二叉树的直径 图解题解

二叉树的直径为什么不一定过根

直径的定义是：树中任意两个节点之间路径长度（边数）的最大值。直觉上最长的路好像该穿过根，其实不然——如果根的一侧子树特别深，最长路径完全可能在那棵子树内部的某个节点处「拐弯」，两头都扎向深处，根本碰不到根。所以任何只在根上算一次的做法都会漏解，必须让树里每个节点都有机会当一次「拐点」。

为什么想到在每个节点算左高加右高

观察最长路径的形状：它一定有一个位置最高的节点，路径在这里拐弯，一头沿左子树往下延伸、一头沿右子树往下延伸（也可能某一头长度为零）。以这个拐点为视角，路径的边数恰好等于「左子树的高度 + 右子树的高度」——每一侧能贡献的最长下探距离就是那侧子树的高度。

于是问题转化为：枚举每个节点作为拐点，算出它的 L + R，取全局最大值。而算某个节点的左右子树高度，本来就是一个经典的递归问题，两件事可以在同一趟遍历里一起做完，这正是树形 DP（在树上做动态规划）的味道。

返回值和答案为什么不是同一个数

这是本题最容易混的点。递归函数 height(node) 返回给父亲的是高度 1 + max(L, R)：站在父亲的角度，路径从父亲下来只能走进你的一条边、再沿着你的某一侧继续往下，所以你能贡献给父亲的只有「单边最深」那一条链。而 L + R 是左右两条链在你这里拼接、拐弯之后的完整路径——它已经拐过弯了，不能再交给父亲往上接，只能就地跟全局答案比大小。

参考代码里这两行各司其职：self.ans = max(self.ans, L + R) 负责收答案，return 1 + max(L, R) 负责给父亲供料。把两者混成一个（比如直接返回 L + R）会让父亲的高度整个算错。

为什么必须用后序遍历

每个节点的计算依赖左右孩子先给出各自的高度，不算完孩子就轮不到父亲——「左、右、根」的处理顺序正是后序遍历。执行时递归一路探到叶子，叶子左右皆空、高度 1、拼接值 0，然后逐层往上回传，每个节点顺手用自己的 L + R 刷一次全局最大值。一趟走完，答案就在全局变量里。

复杂度分析与易错边界

时间 O(n)：每个节点在后序遍历里恰好被访问一次，每次只做常数次比较加法。空间 O(h)：递归栈深度等于树高，最坏退化成链是 O(n)。

两个边界要留心：一是本题答案的口径是边数，若面试官改问「路径上的节点数」，只需在拼接值上加一；二是单节点树没有任何边，直径应为 0——全局答案初始化成 0、叶子的 L + R 恰好也是 0，这个初值天然兜住了该情况。

Python

class Solution:
    def diameterOfBinaryTree(self, root):
        self.ans = 0
        def height(node):
            if not node: return 0
            L = height(node.left)    # 左子树高度
            R = height(node.right)   # 右子树高度
            self.ans = max(self.ans, L + R)  # 穿过本节点的路径
            return 1 + max(L, R)     # 返回给父亲的是高度
        height(root)
        return self.ans

C++

class Solution {
    int ans = 0;
    int height(TreeNode* node){
        if(!node) return 0;
        int L = height(node->left);
        int R = height(node->right);
        ans = max(ans, L + R);   // 穿过本节点
        return 1 + max(L, R);    // 返回高度
    }
public:
    int diameterOfBinaryTree(TreeNode* root){
        height(root);
        return ans;
    }
};

Java

class Solution {
    private int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return ans;
    }
    private int height(TreeNode node) {
        if (node == null) return 0;
        int L = height(node.left);   // 左子树高度
        int R = height(node.right);  // 右子树高度
        ans = Math.max(ans, L + R);  // 穿过本节点的路径
        return 1 + Math.max(L, R);   // 返回给父亲的是高度
    }
}