Sign in Subscribe
算法

二叉树的直径

loser

• 7 min read
Share

给你一棵二叉树的根节点 root，返回该树的直径。

二叉树的直径，是指树中任意两个节点之间最长路径的长度。

这条路径可能经过根节点 root，也可能不经过根节点。

两节点之间路径的长度由它们之间的边数表示。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：取路径 [4,2,1,3] 或 [5,2,1,3]，长度为 3。

示例 2：

输入：root = [1,2]
输出：1

提示：

  • 树中节点数目在范围 [1, 10^4] 内
  • -100 <= Node.val <= 100

后序 DFS：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        depth(root);
        return ans;
    }

private:
    int ans;

    int depth(TreeNode* node) {
        if (node == nullptr)
        {
            return 0;
        }

        int leftDepth = depth(node->left);
        int rightDepth = depth(node->right);

        ans = max(ans, leftDepth + rightDepth);

        return max(leftDepth, rightDepth) + 1;
    }
};

核心思想

这题容易和“二叉树最大深度”联系起来。

对于任意一个节点，如果最长路径经过这个节点，那么这条路径一定是：

左子树中最深的节点 -> 当前节点 -> 右子树中最深的节点

所以经过当前节点的最长路径长度是：

左子树最大深度 + 右子树最大深度

这里要注意：

  • 深度函数返回的是从当前节点向下的最长路径上的节点数
  • 直径要求的是两个节点之间的边数

如果左子树深度是 leftDepth，右子树深度是 rightDepth，那么从左侧最深节点到右侧最深节点的边数正好是：

leftDepth + rightDepth

这题最关键的观察是：

全局直径一定会经过某个节点，并且等于这个节点左右子树最大深度之和。

因此，在递归求每个节点深度的同时，用 leftDepth + rightDepth 更新全局答案即可。

深度函数的含义

定义函数：

int depth(TreeNode* node)

它表示：

以 node 为根的子树，从 node 向下走到最远叶子节点的节点数

如果 node == nullptr，空树深度为 0：

return 0;

如果 node 不为空，先递归计算左右子树深度：

int leftDepth = depth(node->left);
int rightDepth = depth(node->right);

然后当前子树的深度就是：

max(leftDepth, rightDepth) + 1

这个 +1 表示当前节点本身。

如何更新直径

对于当前节点 node，如果最长路径经过它，那么路径会从左子树某个最深节点走到右子树某个最深节点。

路径长度是边数。

左边从当前节点走到最深节点有 leftDepth 条边。

右边从当前节点走到最深节点有 rightDepth 条边。

所以经过当前节点的路径长度是：

leftDepth + rightDepth

代码中用全局变量 ans 记录目前见过的最大直径：

ans = max(ans, leftDepth + rightDepth);

递归遍历所有节点后，ans 就是整棵树的直径。

为什么使用后序遍历

计算当前节点的直径候选值时，需要先知道：

  • 左子树最大深度
  • 右子树最大深度

也就是说，必须先处理左右子树，再处理当前节点。

这正是后序遍历的顺序：

左子树 -> 右子树 -> 根节点

代码中先递归：

int leftDepth = depth(node->left);
int rightDepth = depth(node->right);

然后再更新当前节点对应的直径：

ans = max(ans, leftDepth + rightDepth);

所以这个解法本质上是后序 DFS。

路径不一定经过根节点

题目特别强调，直径路径可能经过根节点，也可能不经过根节点。

例如某棵树的最长路径完全位于左子树内部。

如果只计算根节点的：

root.leftDepth + root.rightDepth

就会漏掉这种情况。

所以算法必须在每个节点都计算一次：

leftDepth + rightDepth

并用全局答案取最大值。

这样无论最长路径经过哪个节点，都会在处理那个节点时被统计到。

边界情况

如果树只有一个节点：

root = [1]

没有任何边，所以直径是 0。

递归中左右子树深度都是 0，更新：

ans = max(ans, 0 + 0) = 0

如果树只有两个节点：

root = [1,2]

最长路径就是这两个节点之间的一条边，所以直径是 1。

如果树退化成一条链，直径就是链上节点数减 1。

正确性证明

我们证明：算法返回的 ans 等于二叉树的直径。

结论 1：depth(node) 正确返回以 node 为根的子树最大深度

如果 node == nullptr，空树没有节点，深度为 0，返回正确。

如果 node 不为空，那么从 node 向下到最远叶子的路径，必然经过左子树或右子树。

左子树最大深度是 leftDepth，右子树最大深度是 rightDepth。

因此当前子树最大深度是：

max(leftDepth, rightDepth) + 1

其中 +1 表示当前节点。

所以 depth(node) 的返回值正确。

结论 2：经过当前节点的最长路径长度是 leftDepth + rightDepth

如果一条最长路径经过当前节点，并且同时向左右两侧延伸，那么左侧最多能延伸到左子树最深节点，长度为 leftDepth 条边。

右侧最多能延伸到右子树最深节点，长度为 rightDepth 条边。

两部分通过当前节点连接后，总边数就是：

leftDepth + rightDepth

如果某一侧为空，对应深度为 0，公式仍然成立。

结论 3：全局直径一定会在某个节点处被统计到

任意两个节点之间的路径，在树中是唯一的。

这条路径上一定存在一个最高的公共节点，可以看作路径连接左右两侧的转折点。

当算法处理这个转折点时，它的左、右子树深度之和至少能覆盖这条路径长度。

因此，真正的全局最长路径一定会在某个节点执行：

ans = max(ans, leftDepth + rightDepth)

时被统计到。

结论 4：算法不会得到超过真实直径的答案

每一次用于更新 ans 的 leftDepth + rightDepth，都对应一条真实存在的路径：

左侧最深节点 -> 当前节点 -> 右侧最深节点

所以它一定不会超过树中任意两点之间最长路径的长度。

因此 ans 不会被更新成非法值。

得出结论

由结论 1 可知，算法能正确计算每个节点左右子树深度。

由结论 2 可知，每个节点对应的直径候选值计算正确。

由结论 3 可知，算法不会漏掉真正的全局直径。

由结论 4 可知，算法不会得到超过真实直径的结果。

因此算法返回的 ans 就是二叉树的直径。

举例理解

以：

root = [1,2,3,4,5]

为例，这棵树可以表示为：

      1
     / \
    2   3
   / \
  4   5

从底向上计算：

节点 左深度 右深度 直径候选
4 0 0 0
5 0 0 0
2 1 1 2
3 0 0 0
1 2 1 3

最大候选值是：

3

对应路径可以是：

4 -> 2 -> 1 -> 3

路径中有 3 条边，所以答案是 3。

复杂度分析

设二叉树节点数为 n，树的高度为 h。

每个节点只会被 DFS 访问一次。

  • 时间复杂度：O(n)
  • 空间复杂度：O(h)

空间复杂度来自递归调用栈。

如果树退化成链，h = n；如果树比较平衡，h = log n。