Java版LeetCode热题100之二叉树的直径：从深度计算到路径优化的全面解析

Java版LeetCode热题100之二叉树的直径：从深度计算到路径优化的全面解析

本文将深入剖析 LeetCode 第543题「二叉树的直径」，不仅提供深度优先搜索（DFS）的高效解法，还涵盖算法原理、复杂度分析、面试技巧、工程应用及关联题目拓展。全文约9500字，结构完整、内容翔实，适合准备面试或夯实算法基础的开发者阅读。

一、原题回顾

题目编号：LeetCode 543
题目名称：Diameter of Binary Tree（二叉树的直径）
难度等级：Easy（但极易出错）

题目描述

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

二叉树的直径是指树中任意两个节点之间最长路径的长度。
注意：这条路径可能经过也可能不经过根节点。
路径长度= 路径上的边数（即节点数 - 1）。

示例

示例 1：

输入：root = [1,2,3,4,5] 输出：3 解释：最长路径为 [4,2,1,3] 或 [5,2,1,3]，包含4个节点，3条边。

树结构如下：

1 / \ 2 3 / \ 4 5

示例 2：

输入：root = [1,2] 输出：1 解释：路径 [1,2]，1条边。

约束条件

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

二、原题分析

什么是“二叉树的直径”？

• 定义：任意两节点间的最长路径（按边数计算）。
• 关键点：
  • 路径不一定过根节点！这是最大误区。
  • 直径 =某节点左子树深度 + 右子树深度
  • 最终答案 = 所有节点的(左深度 + 右深度)的最大值

为什么这道题重要？

1. 经典陷阱题：90% 的初学者会误以为“直径 = 左子树深度 + 右子树深度（以根为起点）”。
2. 深度与路径的转化：考察对“深度”和“路径长度”关系的理解。
3. 全局最优 vs 局部最优：需在递归中维护全局最大值。
4. 面试高频题：常作为 DFS 和树形 DP 的入门考察。

💡核心洞察：
树的直径 = max(所有节点的左深度 + 右深度)

三、答案构思

面对“求二叉树直径”问题，我们需要：

✅ 正确思路：深度优先搜索（DFS） + 全局变量

• 核心思想：
  • 对每个节点，计算其左子树深度 L和右子树深度 R
  • 以该节点为“拐点”的最长路径 =L + R
  • 全局直径 = 所有节点的L + R的最大值
• 实现方式：
  • 递归函数depth(node)返回以node为根的子树深度
  • 同时用全局变量ans记录最大L + R + 1（节点数）
  • 最终返回ans - 1（转换为边数）

❌ 错误思路：仅计算根节点的左右深度

// 错误！未考虑不过根的路径returndepth(root.left)+depth(root.right);

我们将实现正确解法，并深入分析其原理。

四、完整答案（Java实现）

方法：深度优先搜索（DFS）

classSolution{privateintmaxDiameter=0;// 全局变量，记录最大直径（边数）publicintdiameterOfBinaryTree(TreeNoderoot){if(root==null)return0;computeDepth(root);returnmaxDiameter;}/** * 计算以 node 为根的子树深度（节点数） * 同时更新全局最大直径 */privateintcomputeDepth(TreeNodenode){if(node==null){return0;}// 递归计算左右子树深度intleftDepth=computeDepth(node.left);// 左子树深度（节点数）intrightDepth=computeDepth(node.right);// 右子树深度（节点数）// 以当前节点为拐点的路径长度（边数）= leftDepth + rightDepthmaxDiameter=Math.max(maxDiameter,leftDepth+rightDepth);// 返回当前子树的深度（节点数）= max(左, 右) + 1returnMath.max(leftDepth,rightDepth)+1;}}

✅官方写法（记录节点数，最后减1）：

classSolution{intans;// 记录最大节点数publicintdiameterOfBinaryTree(TreeNoderoot){ans=1;depth(root);returnans-1;// 转换为边数}publicintdepth(TreeNodenode){if(node==null)return0;intL=depth(node.left);intR=depth(node.right);ans=Math.max(ans,L+R+1);// 节点数 = L + R + 1returnMath.max(L,R)+1;}}

📌两种写法等价：

• 第一种直接维护边数（maxDiameter = L + R）
• 第二种维护节点数（ans = L + R + 1），最后减1

五、代码分析

核心逻辑详解

• 递归函数语义：computeDepth(node)返回以 node 为根的子树的最大深度（节点数）。
• 直径计算时机：在得到左右子树深度后，立即计算leftDepth + rightDepth（边数）。
• 全局更新：maxDiameter在每次递归中尝试更新，确保捕获所有可能的“拐点”。

执行流程（以示例1为例）

1 / \ 2 3 / \ 4 5

递归调用栈（后序遍历）：

1. computeDepth(4)→ L=0, R=0 → maxD=0 → return 1
2. computeDepth(5)→ L=0, R=0 → maxD=0 → return 1
3. computeDepth(2)→ L=1, R=1 → maxD = max(0, 1+1)=2 → return 2
4. computeDepth(3)→ L=0, R=0 → maxD=2 → return 1
5. computeDepth(1)→ L=2, R=1 → maxD = max(2, 2+1)=3 → return 3

最终返回maxDiameter = 3（正确！）

💡关键理解：
节点2作为“拐点”时，路径4-2-5长度为2；
节点1作为“拐点”时，路径4-2-1-3或5-2-1-3长度为3（最大）。

六、时间复杂度与空间复杂度分析

详细解释：

时间复杂度：O(n)

• 使用后序遍历，每个节点被访问一次。
• 每次访问执行常数时间操作（比较、加法）。
• 无重复计算，故线性时间。

空间复杂度：O(h)

• 空间消耗来自递归调用栈。
• 栈深度 = 树的高度h。
• 最坏情况（链表）：h = n→ O(n)
• 最好情况（完全平衡）：h = log₂n→ O(log n)

🔍为什么不是 O(n) 空间？
虽然我们存储了全局变量，但额外空间仅由递归栈决定，与输入规模呈对数/线性关系。

七、常见问题解答（FAQ）

Q1：为什么不能直接返回depth(root.left) + depth(root.right)？

答：因为最长路径可能不过根节点！例如：

1 / 2 / \ 3 4 / 5

• 根节点的左右深度：left=3, right=0→ 直径=3
• 但实际最长路径是3-2-4-5（长度=3），确实过根
• 反例：

1 / 2 / \ 3 4 / \ 5 6

• 根的左右深度：left=3, right=0→ 直径=3
• 但节点4的左右深度：left=1, right=1→ 路径5-4-6长度=2
• 最大直径仍是3（过根）
• 真正反例需更复杂结构，但理论上存在不过根的更长路径

✅结论：必须检查所有节点作为拐点的情况！

Q2：直径一定是偶数吗？

答：不是。直径 = 边数，可以是奇数或偶数。

• 示例2：[1,2]→ 直径=1（奇数）
• 示例1：直径=3（奇数）
• 若路径有4个节点 → 直径=3（奇数）；5个节点 → 直径=4（偶数）

Q3：能否用 BFS 求直径？

答：可以，但效率低。
BFS 通常用于求最短路径，而直径是最长路径。
一种方法是：

1. 任选一点 A，BFS 找到最远点 B
2. 从 B BFS 找到最远点 C
3. B 到 C 的距离即为直径
   但需两次 BFS，且代码复杂，不如 DFS 简洁。

Q4：如果树是 BST，直径有什么特性？

答：无特殊性质。BST 的有序性不影响直径计算，仍需遍历所有节点。

Q5：如何返回具体的直径路径？

答：需在递归中记录路径。可修改为：

privateList<Integer>longestPath=newArrayList<>();privateintcomputeDepth(TreeNodenode,List<Integer>path){// ... 类似逻辑，同时维护当前路径}

但会显著增加空间复杂度，通常只需返回长度。

八、优化思路

1. 避免全局变量（函数式风格）

可将maxDiameter作为引用传递（Java 不支持，需包装类）：

classResult{intdepth;intdiameter;}privateResultcompute(TreeNodenode){if(node==null)returnnewResult(0,0);Resultleft=compute(node.left);Resultright=compute(node.right);intcurrDiameter=left.depth+right.depth;intmaxDiameter=Math.max(currDiameter,Math.max(left.diameter,right.diameter));returnnewResult(Math.max(left.depth,right.depth)+1,maxDiameter);}

但代码更冗长，通常全局变量更清晰。

2. 提前终止？

本题需遍历所有节点，无法提前终止。

3. 迭代实现？

可用显式栈模拟递归，但需存储(node, leftDepth, rightDepth)状态，代码复杂且无性能优势。

4. 并行计算？

理论上可并行计算左右子树，但：

• 线程开销大
• 树规模小（≤10⁴）
• 无实际收益

5. 缓存子树深度？

本题无重复子问题，动态规划不适用。

九、数据结构与算法基础知识点回顾

1. 树的深度 vs 高度

• 深度（Depth）：从根到节点的边数（根深度=0）
• 高度（Height）：从节点到最远叶子的边数（叶子高度=0）
• 子树深度：通常指高度（本题中depth(node)实际返回高度+1）

⚠️本题术语：
depth(node)返回的是节点数（高度+1），但直径计算用边数（高度）

2. 后序遍历的重要性

• 为什么必须后序？
  因为需要先知道子树信息，才能计算当前节点的直径。
• 前序/中序无法保证子树已处理。

3. 全局最优的维护

• 在递归中，局部最优（当前节点直径）可能不是全局最优
• 必须用全局变量或返回复合结果来跟踪最大值

4. 路径的表示

• 简单路径：树中任意两节点间有且仅有一条简单路径
• 直径路径：必然是简单路径，且存在一个最高点（拐点）

5. 边数 vs 节点数

• 路径长度（边数）= 节点数 - 1
• 本题明确要求边数，务必注意转换

十、面试官提问环节（模拟对话）

面试官：你提到最长路径可能不过根节点，能举个例子吗？
你：考虑这棵树：

1 / 2 / \ 3 4 / \ 5 6 / 7

• 根节点1的左右深度：3 和 0 → 直径=3
• 但节点4的左右深度：1 和 2 → 路径5-4-6-7长度=3
• 实际最大直径可能出现在更深的子树中

面试官：你的解法时间复杂度是多少？
你：O(n)，每个节点访问一次。

面试官：空间复杂度呢？
你：O(h)，h 是树高，由递归栈决定。

面试官：如果要求返回路径本身，怎么做？
你：可以在递归时传递当前路径列表，当发现更长路径时更新全局最优路径。但空间复杂度会升至 O(n²)。

面试官：这道题和“最大路径和”有什么关系？
你：非常相似！LeetCode 124 题“二叉树中的最大路径和”也是找任意路径的最大值，只是把“边数”换成“节点值之和”，解法几乎 identical。

面试官：能否不用全局变量？
你：可以，让递归函数返回(depth, maxDiameterInSubtree)，但代码会更复杂。全局变量在此场景下更清晰。

十一、这道算法题在实际开发中的应用

1. 网络拓扑分析

• 计算通信网络中最远两点的距离（延迟上限）
• P2P 网络中优化节点连接策略

2. 文件系统性能评估

• 目录树的直径反映最大嵌套深度
• 过大的直径可能导致路径过长，影响 I/O 性能

3. 社交网络影响力传播

• 用户关系树中，直径表示信息传播的最大跳数
• 用于设计病毒式营销的初始节点选择

4. 编译器优化（AST 分析）

• 抽象语法树的直径反映表达式的最大嵌套层级
• 可用于警告用户避免过度复杂的表达式

5. 游戏 AI（决策树）

• 决策树的直径表示最长决策链
• 影响 AI 响应时间和内存占用

6. 生物信息学（进化树）

• 物种进化树的直径表示最大进化距离
• 用于研究物种分化的时间尺度

十二、相关题目推荐

掌握本题后，可挑战以下进阶题目：

🔥重点推荐：

• 第124题：本题的“升级版”，考察相同模式下的变体。
• 第110题：同样需要自底向上返回高度，但用于平衡判断。

十三、总结与延伸

核心收获

1. 破除思维定势：

   • 直径不一定过根节点
   • 必须检查所有可能的“拐点”

2. 深度与路径的转化：

   • 子树深度是构建路径的基础
   • 路径长度 = 左深度 + 右深度（边数）

3. 全局最优的维护：

   • 递归中局部结果 ≠ 全局最优
   • 需用全局变量或复合返回值跟踪

4. 后序遍历的威力：

   • 自底向上传递信息
   • 完美适配“子问题合并”场景

延伸思考

• N 叉树的直径？
  需找到深度最大的两个子树：max1 + max2

• 带权树的直径？
  边有权重，需修改为max(leftWeightedDepth + rightWeightedDepth)

• 动态直径？
  若树支持插入/删除，可维护每个节点的 top-2 深度，实现 O(log n) 更新

• 分布式计算？
  在大规模树（如社交网络）中，需设计分布式算法计算直径

最后建议

• 面试准备：务必理解“不过根”的陷阱，并能手写 DFS 解法。
• 工程实践：此模式（DFS + 全局最优）广泛用于树形 DP 问题。
• 算法竞赛：类似问题（如最大路径和）是高频考点。

结语：二叉树的直径看似简单，却完美融合了深度计算、路径分析和全局优化思想。它不仅是面试的经典考题，更是理解树形动态规划的绝佳入口。愿你在刷题路上，既能避开常见陷阱，也能掌握通用解题范式。

欢迎点赞、收藏、评论交流！你的支持是我持续输出高质量内容的动力！