LeetCode 543. 二叉树的直径

2026-08-03 HGNULB 约 4 分钟

文章信息 18 个分类 6 个标签

分类

LeetCode CodeTop 简单已解决已掌握 50-100 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度网易小米亚马逊 LeetCode 热题 100

题目描述

✅ 543. 二叉树的直径

题意分析

求二叉树中任意两个节点之间最长路径的长度。这里有两个必须先钉死的定义，否则后面全错。

第一，长度按边数计，不是节点数：路径上有 k 个节点，长度就是 k - 1。由此推出单节点树的直径是 0，这是最小的正确性检验用例。

第二，这条最长路径不必经过根节点：它可以完全藏在某棵子树里，只要求路径上相邻节点有父子边相连、且不走回头路。任何只盯着根看的做法都会漏解。

约束上节点数最多 $10^4$，树可能退化成一条链，方案需要线性或接近线性，同时要留意递归深度可能达到 $10^4$。节点值与答案完全无关。

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

核心思路

问题关键：最长路径不一定经过根，但一定有唯一的最高点。若某节点左右子树的高度分别为 left、right，以它为最高点的最长路径包含 left + right 条边。

为什么选该解法：若对每个节点重新计算高度，最坏会退化到 $O(n^2)$。后序 DFS 先拿到左右高度，再同时更新直径，每个节点只处理一次。

不变量/状态定义：height(node) 返回从 node 向下的最长路径所含节点数，空节点返回 0；全局 diameter 保存已处理节点中的最大直径（边数）。递归向父节点只能返回较高的一侧，而左右两侧之和只用于更新答案。每条路径都会在自己的最高点被计算，因此不会漏解。

解题步骤

将 diameter 初始化为 0，从根节点开始后序 DFS。

空节点返回高度 0；递归得到左右子树高度。

用 left + right 更新直径。

向父节点返回 max(left, right) + 1。

例如 [1,2,3,4,5] 中，节点 2 得到高度 1、1，候选直径为 2；根节点得到 2、1，最终直径为 3。

代码实现

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(n)$。

关键点总结

返回值是供父节点使用的单侧高度，全局答案才接收左右两侧之和。

直径的最高点可能是任意节点，必须在每个节点更新答案。

空节点高度定义为 0，left + right 才恰好表示边数。

易错点总结

只在根节点计算直径：最长路径可能完全位于某棵子树中。

把节点数当边数：单节点树的直径是 0，不是 1。

向父节点返回 left + right + 1：父节点会把一条已经分叉的路径再次拼接，形成非法路径。

把 height(root) 当答案：高度和直径是两个不同的状态。

相似题目

题目	难度	考察点
124. 二叉树中的最大路径和	困难	同款骨架但贡献带权可负，需与 0 截断
687. 最长同值路径	中等	深度延伸附加「值相等」条件，不满足即清零
LCR 051. 二叉树中的最大路径和	困难	124 的镜像题，检验贡献法是否真正内化
1245. 树的直径	中等	无根一般树上求直径，需邻接表建图或两次 BFS