hot 100 第三十八题 39.二叉树的直径-育师

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

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

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

示例 1：

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

示例 2：

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

这是二叉树的直径问题，求任意两个节点之间路径的最大长度（经过的边数）。

核心思路

后序遍历 + 全局变量：直径 = 左子树深度 + 右子树深度，在计算深度的过程中更新最大直径。

关键认知: - 直径不一定经过根节点 - 对每个节点，经过它的最长路径 = 左子树高度 + 右子树高度 - 遍历所有节点，记录最大值

示例: 1 / \ 2 3 / \ 4 5 经过节点2的路径: 4→2→5 (长度2) 这是整棵树的直径

解法：递归（最优）

代码

class Solution { private int maxDiameter = 0; // 全局变量记录最大直径 public int diameterOfBinaryTree(TreeNode root) { depth(root); return maxDiameter; } // 计算深度的同时更新直径 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); // 返回当前节点的深度 return Math.max(leftDepth, rightDepth) + 1; } } ``` ### 详细演示 ``` 二叉树: 1 / \ 2 3 / \ 4 5 递归调用树: depth(1) ├─ depth(2) │ ├─ depth(4) │ │ ├─ depth(null) → 0 │ │ └─ depth(null) → 0 │ │ 更新: maxDiameter = max(0, 0+0) = 0 │ │ 返回: max(0,0)+1 = 1 │ │ │ ├─ depth(5) │ │ ├─ depth(null) → 0 │ │ └─ depth(null) → 0 │ │ 更新: maxDiameter = max(0, 0+0) = 0 │ │ 返回: max(0,0)+1 = 1 │ │ │ 更新: maxDiameter = max(0, 1+1) = 2 ✓ (路径 4→2→5) │ 返回: max(1,1)+1 = 2 │ ├─ depth(3) │ ├─ depth(null) → 0 │ └─ depth(null) → 0 │ 更新: maxDiameter = max(2, 0+0) = 2 │ 返回: max(0,0)+1 = 1 │ 更新: maxDiameter = max(2, 2+1) = 3? 不，仍是2 (经过根节点1的路径长度是2+1=3，但没有超过2)

边界情况

// 1. 空树 root = null 返回 0 // 2. 单节点 root = [1] 深度0, 直径0 返回 0 // 3. 两节点 1 / 2 左深度1, 右深度0 直径 = 1+0 = 1 返回 1 // 4. 链状树 1 \ 2 \ 3 \ 4 节点4: 直径0 节点3: 直径1 节点2: 直径2 节点1: 直径3 返回 3 // 5. 完全二叉树 1 / \ 2 3 / \ / \ 4 5 6 7 节点2: 左1+右1=2 节点3: 左1+右1=2 节点1: 左2+右2=4 返回 4

测试用例

// 测试1 root = [1,2,3,4,5] 1 / \ 2 3 / \ 4 5 输出: 3 (路径 4→2→5 或其他) // 测试2 root = [1,2] 1 / 2 输出: 1 // 测试3 root = [1] 输出: 0 // 测试4 (直径不过根) root = [1,2,null,3,null,4] 1 / 2 / 3 / 4 输出: 3

常见错误

错误1：混淆深度和直径

// ✗ 错误（直接返回深度） public int diameterOfBinaryTree(TreeNode root) { return depth(root); // 这是深度，不是直径！ } // ✓ 正确（深度过程中记录直径） private int maxDiameter = 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return maxDiameter; // 返回记录的最大直径 }

错误2：忘记更新全局变量

// ✗ 错误（只计算深度，没更新直径） private int depth(TreeNode node) { if (node == null) return 0; int left = depth(node.left); int right = depth(node.right); return Math.max(left, right) + 1; // 忘记更新maxDiameter } // ✓ 正确 private int depth(TreeNode node) { if (node == null) return 0; int left = depth(node.left); int right = depth(node.right); maxDiameter = Math.max(maxDiameter, left + right); // 关键！ return Math.max(left, right) + 1; }

错误3：返回值错误

// ✗ 错误（返回直径而不是深度） private int depth(TreeNode node) { if (node == null) return 0; int left = depth(node.left); int right = depth(node.right); return left + right; // 这是直径，不是深度！ } // ✓ 正确 return Math.max(left, right) + 1; // 返回深度

复杂度分析

时间复杂度: O(n) — 每个节点访问一次
空间复杂度: O(h) — 递归栈深度
- 平衡树: O(log n)
- 链状树: O(n)

不使用全局变量的版本

class Solution { public int diameterOfBinaryTree(TreeNode root) { return dfs(root)[1]; // 返回直径 } // 返回 [深度, 直径] private int[] dfs(TreeNode node) { if (node == null) return new int[]{0, 0}; int[] left = dfs(node.left); int[] right = dfs(node.right); int depth = Math.max(left[0], right[0]) + 1; int diameter = Math.max( left[0] + right[0], // 经过当前节点的路径 Math.max(left[1], right[1]) // 子树中的最大直径 ); return new int[]{depth, diameter}; } }