543. 二叉树的直径

难度：🟢 Easy | 标签：树、DFS | 状态：⬜ LeetCode 链接

思路

直径 = 任意两节点路径上的边数最大值。 对每个节点：「经过它的最长路径」= 左子高度 + 右子高度。 DFS 返回高度，过程中更新全局直径。

代码

class Solution {
    int best = 0;
    int depth(TreeNode* r) {
        if (!r) return 0;
        int l = depth(r->left), rt = depth(r->right);
        best = max(best, l + rt);
        return 1 + max(l, rt);
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return best;
    }
};

复杂度

• 时间 O(n)，空间 O(h)

易错 / 回顾

• 返回值（高度）和答案（直径）是两套
• 直径计边数不计点数：l + r 不需要 +1
• 通用模板：求”经过本节点的某属性”全部走这套