024 · Diameter of Binary Tree

algorithm

Published

May 28, 2026

My First Thoughts

这道题第一眼会觉得比前几道树题更复杂一点，因为它不是单纯从根节点往下走。

题目要找的是树里任意两个节点之间的最长路径，也就是最长路径上有多少条边。

一开始最自然的想法是：先判断最长路径会不会经过 root。

如果它经过 root，那路径大概就是：

左边某个最深节点 -> root -> 右边某个最深节点

这时答案应该和左右两边的最大长度有关：

left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)

然后把左右两边连起来，得到一条经过 root 的路径。

可是题目里最长路径不一定经过整棵树的根节点。

比如 root.left 里面本身有两个很深的分支，而 root.right 很短，那最长路径可能完全在左子树内部形成。

所以会继续想：是不是需要比较 root.left 内部的两条分支，和 root.right 这边的长度？

大概像这样：

如果 root.left 里面的左分支 + 右分支
比 root.right 这边还长，
那最长路径可能就不必经过 root

反过来也一样：

如果 root.right 内部两条分支更长，
那最长路径可能就在右子树里面

如果都不是，那答案可能就是经过 root 的：

root.left 的最长向下路径 + root.right 的最长向下路径

然后继续往下递归：把 root.left 当成新的 root，再做同样的比较；把 root.right 当成新的 root，也做同样的比较。

这里会自然想到复用前面的 maxDepth：

def maxDepth(root):
    if root is None:
        return 0

    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)

    return 1 + max(left_depth, right_depth)

如果对每个节点都能拿到左右最大深度，就能知道经过当前节点的路径长度。

这个思路里面有一个正确感觉：直径确实和左右分支的最大深度有关。

但具体怎么比较，还没有整理清楚。

Why That Is Not Enough

上面的想法问题不在于“方向完全错了”，而在于比较规则不清晰。

它试图先判断：

最长路径到底经过 root，还是位于 root.left / root.right 里面？

然后又想用：

某个子节点内部的两条分支
和另一个子节点的最长分支

来决定路径应该走哪边。

这样会让状态定义变得复杂。

因为对一个节点来说，至少有两件不同的事情：

以这个节点为中间连接点时，能形成多长的路径
从这个节点返回给父节点时，应该返回哪一条向下路径的长度

这两个问题不能混在一起。

例如，root.left 内部的最长直径，可能来自它的左分支加右分支；但当 root.left 向 root 返回高度时，它不能同时返回左右两条分支。

因为一条从父节点继续往下走的路径，只能选择一边：

root -> root.left -> 左边更深的一条分支

或者：

root -> root.left -> 右边更深的一条分支

不能从 root 走到 root.left 之后，又同时走进 root.left 的左右两边。

所以，“子节点内部两条分支的和”和“这个子节点返回给父节点的最长单边路径”是两个不同的值。

如果把它们放在同一个比较里，就容易不知道当前算的是：

已经完成的一条直径

还是：

可以继续往父节点延伸的一条路径

另外，如果为了处理这些情况，写成“每到一个节点都重新调用 maxDepth 去算左边、右边、子节点内部”，还会出现重复计算。

比如在 root 这里调用：

maxDepth(root.left)

它已经扫过了左子树。

之后递归到 root.left 时，又会重新计算它下面很多节点的深度。

这样就和上一题 Balanced Binary Tree 的直观解法很像：方向接近，但“求高度”和“更新答案”分成了多次递归，导致同一批高度信息被反复求。

这道题真正要解决的是：

怎么把“返回给父节点的单边高度”和“当前节点形成的直径候选值”分开？

整理清楚这个区别之后，正解就简单很多。

Final Idea

正确的转折点是换一个问题来问。

不要先判断：

最长路径到底在左边、右边，还是经过 root？

而是问：

对树里的每一个节点 N，假设最长路径的最高点就是 N，也就是路径在 N 这里连接左右两边，那么这条路径有多长？

这样问题就清楚了。

对某个节点 N 来说，如果一条路径以 N 作为最高点，那么它一定长成这样：

左子树中某个最深节点 -> N -> 右子树中某个最深节点

为了让这条路径尽量长，左边应该取左子树的最大深度，右边应该取右子树的最大深度。

所以对每个节点，只需要知道两个值：

left_depth
right_depth

这里的 depth 可以沿用前面最大深度题里的意思：

depth(node) 返回从 node 往下走，最多能经过多少个节点。

空节点返回 0，叶子节点返回 1。

这样看起来 depth 返回的是节点数，但当前节点的直径候选值刚好可以写成：

left_depth + right_depth

为什么这里不用再减 1？

因为 left_depth 表示从左孩子往下最多有多少个节点，right_depth 表示从右孩子往下最多有多少个节点。

当路径经过当前节点时：

左边节点数 + 当前节点 + 右边节点数

这是节点数。

但题目要的是边数。节点数要减 1。

同时这里左右两边没有把当前节点算进去，所以：

路径节点数 = left_depth + 1 + right_depth
路径边数 = left_depth + right_depth

所以以当前节点作为最高点时，路径长度就是：

left_depth + right_depth

然后对树里的每个节点都做一次这个计算，取最大值，就是整棵树的直径。

接下来还要处理递归返回值。

depth(node) 返回给上一层的，不能是当前子树内部的直径。

原因是：上一层如果要构造一条经过父节点的路径，从 node 这一侧只能选择一条向下路径，不能同时使用 node 的左右两边。

所以 depth(node) 仍然只返回高度：

return 1 + max(left_depth, right_depth)

这个返回值给父节点使用。

直径答案则单独用 answer 记录。

每访问一个节点，递归函数做两件事：

用左右深度更新答案：answer = max(answer, left_depth + right_depth)
返回当前子树的最大深度：1 + max(left_depth, right_depth)

这就是这道题的核心：

递归返回高度给父节点，同时在递归过程中更新全局最大直径。

Why It Works

任意一条二叉树路径，如果它是从一个节点走到另一个节点，中间一定会有一个“最高的连接点”。

从这个连接点看，这条路径就是：

左边往下的一条路径 + 当前节点 + 右边往下的一条路径

也就是说，任何可能成为答案的路径，都会在某个节点被表示成：

left_depth + right_depth

递归会访问树中的每一个节点，所以每个节点作为连接点的情况都会被检查一次。

depth(node) 的返回值只负责一件事：

告诉父节点，从我这里往下最多能走多深。

而 answer 负责记录另一件事：

到目前为止，见过的最长路径有多少条边。

这两个状态分工清楚，就不会互相混在一起。

Code

def diameterOfBinaryTree(root):
    answer = 0

    def depth(node):
        nonlocal answer

        if node is None:
            return 0

        left_depth = depth(node.left)
        right_depth = depth(node.right)

        answer = max(answer, left_depth + right_depth)

        return 1 + max(left_depth, right_depth)

    depth(root)
    return answer

Complexity

Time	\(O(n)\) - 每个节点只访问一次，访问时同时计算高度并更新直径
Space	\(O(h)\) - 递归调用栈的深度等于树的高度 `h`，最坏情况下可以到 \(O(n)\)

Takeaway

这题的关键是分清递归返回值和最终答案。递归返回的是“当前节点往下的最大深度”，这是父节点需要的信息；最终答案是“任意两个节点之间的最长路径”，可以在每个节点用 left_depth + right_depth 顺手更新。树的递归题里，返回值不一定就是最终答案，它也可以只是帮助上一层继续计算的中间信息。

← Quiz