543. 二叉树的直径
一句话套路后序:过每个结点的直径=左高+右高
题目描述
给你一棵二叉树的根节点,返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1:
输入:root = [1,2,3,4,5] 输出:3 解释:3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2:
输入:root = [1,2] 输出:1
提示:
- 树中节点数目在范围
[1, 104]内 -100 <= Node.val <= 100
思路
时间
O(n)空间
O(h)思路
直径 = 某个结点的「左深 + 右深」(按边数)。
递归函数只返回「高度」,直径用引用参数在沿途更新 —— 这就是「一个返回值不够用」时的标准处理方式,Q124 完全同构。
易错
返回高度时是 1+max(l,r),而更新答案时是 l+r(边数),别写成 l+r+1。
图解
二叉树(来自本仓库测试数据,
nullopt 表示空位)逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0543 {
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int best = 0;
height(root, best);
return best;
}
private:
static int height(TreeNode* n, int& best) {
if (!n) return 0;
int l = height(n->left, best);
int r = height(n->right, best);
best = max(best, l + r); // 经过 n 的最长路径(边数)
return 1 + max(l, r);
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0543::Solution s;
TreeNode* a = buildTree({1, 2, 3, 4, 5});
CHECK_EQ(s.diameterOfBinaryTree(a), 3); // 4-2-1-3 或 5-2-1-3
freeTree(a);
TreeNode* b = buildTree({1, 2, nullopt, 3, nullopt, 4, nullopt, 5}); // 斜链
CHECK_EQ(s.diameterOfBinaryTree(b), 4);
freeTree(b);
CHECK_EQ(s.diameterOfBinaryTree(nullptr), 0);