跳至主要內容

二叉树的直径——每个节点作为转折点的枚举思想

老张2026/4/30大约 8 分钟

二叉树的直径——每个节点作为转折点的枚举思想

适读人群：Java 后端工程师、LeetCode 刷题的同学 | 阅读时长：约18分钟 | 难度：Easy

开篇故事

543 题和 124 题是一对好兄弟，思路几乎完全一样：枚举每个节点作为路径的"最高点"（或"转折点"），局部计算路径长度/路径和，维护全局最大值。

直径题比最大路径和题简单，因为不涉及负权重问题，所有路径长度都是非负的。但有一个坑：很多人以为直径一定经过根节点，所以直接用 maxDepth(root.left) + maxDepth(root.right) 来求，然后在某些用例上失败了。

比如这棵树：

    1
   / \
  2   3
 / \
4   5

直径是 4 或 5 到 3 的路径：4(或5)->2->1->3，长度为 4。但 4 号节点和 5 号节点到 3 的路径都经过节点 1（根）。

但如果左子树更深的话：

      1
     /
    2
   / \
  4   5
 /
6

直径是 6->4->2->5，长度为 3，根本不经过根节点 1。

所以"直径经过根节点"是不正确的，必须枚举所有节点作为转折点。

一、题目解析

题目：LeetCode 543. 二叉树的直径

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

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root。

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

示例：

输入：root = [1,2,3,4,5]
输出：3
解释：3 是路径 [4,2,1,3] 或 [5,2,1,3] 的长度

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

注意： 路径长度是边的数量，不是节点数量。

考点梳理：

  1. 树的深度（高度）计算
  2. 直径 = 两子树深度之和（以某节点为转折点）
  3. 全局变量记录最大值
  4. 节点数和边数的转换（路径中有 n 个节点，就有 n-1 条边）

二、解法一：暴力解法——对每个节点单独求深度

思路

对每个节点分别求左子树深度和右子树深度，计算经过该节点的最长路径，取全局最大值。

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        
        // 以当前节点为转折点的直径
        int localDiameter = depth(root.left) + depth(root.right);
        
        // 递归求左右子树的直径
        int leftDiameter = diameterOfBinaryTree(root.left);
        int rightDiameter = diameterOfBinaryTree(root.right);
        
        return Math.max(localDiameter, Math.max(leftDiameter, rightDiameter));
    }
    
    private int depth(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(depth(node.left), depth(node.right));
    }
}

复杂度分析

  • 时间复杂度：O(n^2)。对每个节点调用 depth，depth 本身是 O(n)。
  • 空间复杂度：O(n)。递归栈。

三、解法二：DFS 递归 + 全局变量（标准解法）

思路

和 124 题完全相同的模式：把"计算深度"和"更新全局直径"合并到一次后序遍历里。

递归函数返回以当前节点为根的子树的深度（即从当前节点出发向下的最长路径的边数）。同时，每到一个节点，把它作为路径转折点，用左深度+右深度更新全局最大直径。

节点数 vs 边数的换算：

  • depth 函数返回从当前节点到最远叶节点的边数（空节点返回 -1 或改用返回边数的写法）
  • 实际上返回节点数-1更直观

有两种等价写法：

  1. depth 返回"节点数"（空节点返回 0），直径更新时 left + right 直接就是边数（因为左子树 left 个节点包含 left 条边到达转折点，右边同理）
  2. depth 返回"边数"（空节点返回 -1），直径更新时 left + right + 2 是边数

完整代码

class Solution {
    private int maxDiameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return maxDiameter;
    }
    
    // 返回以 node 为根的子树的高度（边数），空节点返回 0
    // 注意：这里返回的是"从 node 出发向下最多走几步"，空节点是 0 步
    private int depth(TreeNode node) {
        if (node == null) return 0;
        
        int leftDepth = depth(node.left);
        int rightDepth = depth(node.right);
        
        // 以当前节点为转折点的路径长度（边数）= 左深度 + 右深度
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
        
        // 返回当前节点的深度（向上传递时 +1）
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

复杂度分析

  • 时间复杂度：O(n)。每个节点只被访问一次。
  • 空间复杂度：O(n)。递归栈深度为树的高度，最坏 O(n)。

提交结果：时间击败约 100% 用户，空间击败约 70% 用户。

四、解法三：最优解法——迭代版本（后序遍历 + 栈）

思路

用显式栈实现后序遍历，同时维护每个节点的深度信息。相比递归版本，规避了极端情况下的栈溢出风险。

Mermaid 图——以各节点为转折点枚举

完整代码（迭代版本）

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        
        int maxDiameter = 0;
        Map<TreeNode, Integer> depthMap = new HashMap<>();  // 记录每个节点的深度
        
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        
        // 后序遍历（先处理子节点，再处理父节点）
        // 使用访问标记
        Set<TreeNode> visited = new HashSet<>();
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            
            // 如果左右子节点都已处理完，处理当前节点
            boolean leftDone = node.left == null || visited.contains(node.left);
            boolean rightDone = node.right == null || visited.contains(node.right);
            
            if (leftDone && rightDone) {
                stack.pop();
                visited.add(node);
                
                int leftDepth = depthMap.getOrDefault(node.left, 0);
                int rightDepth = depthMap.getOrDefault(node.right, 0);
                
                maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
                depthMap.put(node, 1 + Math.max(leftDepth, rightDepth));
            } else {
                if (!rightDone) stack.push(node.right);
                if (!leftDone) stack.push(node.left);
            }
        }
        
        return maxDiameter;
    }
}

复杂度分析

  • 时间复杂度：O(n)。每个节点进出栈一次。
  • 空间复杂度：O(n)。depthMap 和 visited 各 O(n)，栈 O(n)。

注意：迭代版本空间消耗反而更大（HashMap 和 HashSet），但避免了 Java 的递归栈溢出风险，在极深的树（如 30000 个节点的链状树）上更稳健。

五、举一反三

同类题目

LeetCode 124. 二叉树中的最大路径和 直径的加权版本，每条边有权重（节点值），思路完全相同。

LeetCode 687. 最长同值路径 以每个节点为转折点，找同值节点连续延伸的最大长度，同样模式。

LeetCode 1245. 树的直径（图上的树） 给一棵无根树（以邻接表表示），找直径。用 BFS/DFS 两次：第一次找到最远节点 u，第二次从 u 出发找最远节点 v，uv 距离即为直径。

"每个节点为转折点"通用模板

int globalMax = 0;  // 或 Integer.MIN_VALUE（有负值时）

int dfs(TreeNode node) {
    if (node == null) return 0;
    int left = dfs(node.left);
    int right = dfs(node.right);
    
    // 以当前节点为转折点，更新全局答案
    globalMax = Math.max(globalMax, left + right /* 或 left + right + 当前节点的贡献 */);
    
    // 只能向一侧延伸，返回单侧最优值
    return 1 + Math.max(left, right);
}

六、踩坑实录

坑一：以为直径一定经过根节点

这是这道题最常见的错误理解。直径可以在任意子树内，不一定经过根节点。必须枚举每个节点作为转折点。

坑二：路径长度用节点数而不是边数

题目明确说路径长度是边数，而不是节点数。空节点深度应该是 0（没有边），叶节点深度是 0（不能往下延伸），叶节点的父节点深度是 1（有一条边通向叶节点）。

如果把空节点深度设为 -1，叶节点深度为 0，同样可以工作，但在更新直径时要用 left + right + 2（左右各增加 1，补偿两端的 -1 变成 0 的计算）。两种写法都正确，选一种统一。

坑三：单节点树的直径

单节点树没有边，直径为 0。代码里 left = depth(null) = 0，right = depth(null) = 0，maxDiameter = max(0, 0+0) = 0，正确。

坑四：初始化 maxDiameter 时忘记考虑负值情况

543 题的直径是边数，不可能为负，初始化为 0 完全正确。但如果把类似思路用到 124 题（最大路径和），节点值可以为负，初始化必须用 Integer.MIN_VALUE，而不是 0。混淆了两道题的初始化方式是一个坑。

坑五：把 depth 函数用于计算全局直径的方式写错

// 错误：只计算了经过根节点的直径
return depth(root.left) + depth(root.right);  // 漏了左右子树内部的直径

正确做法是递归地在每个节点处更新全局变量，不能只看根节点处的情况。

七、总结

543 题是 124 题的简化版，学完 124 再做 543，会发现代码几乎一样。这两道题合起来构成了"树上路径问题"的核心模式：

枚举每个节点作为转折点，计算经过该节点的最优路径，维护全局最大值；递归返回时只传递单侧延伸的信息。

这个模式在后续题目里会反复出现，建议深度理解而不是机械记忆代码。理解了模式，变体题自然手到擒来。

编辑此页
最近更新:
贡献者: xiaozhangge