LeetCode 543. 二叉树的直径

约 5 分钟
文章信息 19 个分类 3 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 50-100 LeetCode 热题 100 腾讯 字节 阿里 微软 亚马逊 美团 小米 百度 网易 快手 贝壳 猿辅导
标签
深度优先搜索 树 二叉树

题目描述

✅ 543. 二叉树的直径

image-20260928194331209

image-20260928194331210

题意分析

二叉树的直径是任意两个节点之间最长路径的边数，返回这个长度。路径沿父子边连接，不能重复经过同一个节点；起点和终点可以位于任意位置，最长路径不一定经过整棵树的根。

这里计算的是边数，不是节点数，也不是节点值的和。只有一个节点时没有边，直径为 0。从根向下的最长路线只能得到树的高度，而直径还可能从某个节点的左侧经过该节点，继续走向它的右侧。

解法：后序 DFS 计算高度并更新直径

核心思路

[!blue]

任意一条路径都有一个离根最近的节点。把它作为路径的最高点，路径最多由左子树的一条向下路线、当前节点、右子树的一条向下路线组成。枚举每个节点作为最高点，再取所有候选的最大值，就不会漏掉完全位于子树内部的最长路径。

定义 height(node) 为从当前节点向下走到最远叶子的节点数。空节点高度为 0，非空节点高度为 max(leftHeight, rightHeight) + 1。它只返回一侧高度，因为父节点接入后，路径不能再同时向当前节点的左右两侧分叉。

当前节点连接左侧最深路线所用的边数，恰好等于 leftHeight：左子树路线内部有 leftHeight - 1 条边，再加上当前节点连到左孩子的一条边；左子树为空时贡献为 0。右侧同理，因此以当前节点为最高点的最长路径边数就是 leftHeight + rightHeight。

递归先拿到左右高度，用它们的和更新全局 diameter，再把较大高度加一返回给父节点。这样一次后序遍历同时完成“向上提供高度”和“在本层更新直径”两项工作，不必在每个节点重新遍历子树求高度。

全局答案初始化为 0。叶子节点左右高度都为零，候选直径自然是零；只有一侧子树时，另一侧的零贡献也能直接套用同一公式。

解题步骤

  1. 将直径初始化为 0，从根调用 height。
  2. 空节点返回高度 0。
  3. 递归求出 leftHeight 和 rightHeight，先处理孩子，再处理当前节点。
  4. 用 leftHeight + rightHeight 更新全局最大直径。
  5. 返回 max(leftHeight, rightHeight) + 1，供父节点计算单侧延伸长度。
  6. 根节点处理完后返回全局直径，而不是根的高度。

代码实现

class Solution {
    private int diameter;

    public int diameterOfBinaryTree(TreeNode root) {
        // 每次调用重新统计，避免复用对象时沿用旧答案。
        diameter = 0;
        height(root);

        return diameter;
    }

    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        // 左右高度按节点数计算，相加正好得到经当前节点的路径边数。
        diameter = Math.max(diameter, leftHeight + rightHeight);

        // 向父节点只返回单侧高度，不能把两条分支一起延伸。
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

func diameterOfBinaryTree(root *TreeNode) int {
    ans := 0

    var height func(*TreeNode) int
    height = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        leftHeight := height(node.Left)
        rightHeight := height(node.Right)
        // 左右高度按节点数计算，相加正好得到经当前节点的路径边数。
        if leftHeight+rightHeight > ans {
            ans = leftHeight + rightHeight
        }
        // 向父节点只返回单侧高度，不能把两条分支一起延伸。
        if leftHeight > rightHeight {
            return leftHeight + 1
        }
        return rightHeight + 1
    }

    height(root)
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点只计算一次高度并更新一次直径，不重复扫描子树。
  • 空间复杂度：$O(h)$，h 为树高，来自递归栈。平衡树为 $O(\log n)$，链状树最坏为 $O(n)$。

关键点总结

[!green]

  • 高度按节点数定义，经过当前节点的候选直径按边数计算，公式分别为 max(left, right) + 1 和 left + right。
  • 返回值只能延伸一侧，全局答案可以组合两侧，二者不能混用。
  • 每个节点都可能成为最长路径的最高点，必须逐节点更新答案。

易错点总结

[!yellow]

  • 只在根节点合并左右高度，会漏掉完全位于某棵子树中的最长路径。
  • 把候选直径写成 leftHeight + rightHeight + 1，得到的是路径节点数，比边数多一。
  • 向父节点返回左右高度之和，会把已经连接两侧的路径再接到父节点，形成分叉。
  • 返回 height(root) 只能得到高度，不能代表任意两节点之间的最大距离。
  • Java 的成员变量 diameter 应在每次入口调用时归零，避免复用同一对象时留下上一次答案。

相似题目

题目 难度 关联与区别
124. 二叉树中的最大路径和 困难 同样在节点处组合左右贡献，本题按边数计长度，原题按节点权值求和并丢弃负贡献。
687. 最长同值路径 中等 同样组合两侧延伸长度，原题只允许相邻值相等，本题没有数值限制。
104. 二叉树的最大深度 简单 后序返回子树高度并在根处合并信息；本题合并左右向下路径得到直径，该题取两侧最大高度加一。
110. 平衡二叉树 简单 后序返回子树高度并在根处合并信息；本题合并左右向下路径得到直径，该题额外验证两侧高度差。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/83624487
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！