二叉树的直径
Diameter of Binary Tree
返回二叉树中任意两个节点之间最长路径的边数，路径不一定经过根。
在力扣中练习题目描述
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2] 输出：1
提示：
- 树中节点数目在范围
[1, 104]内 -100 <= Node.val <= 100
解题思路
主解法
后序 · 高度与直径同时算
每个节点返回一条最长链，同时用左右高度更新答案
路径在某个节点处“拐弯”：从它出发，向左走一条最长链，向右走一条最长链，拼起来就是经过它的最长路径。长度等于 左高 + 右高。
对每个节点都做一次这个计算，再取最大值。关键在于：向父节点返回时，只能返回一条链，不能把左右两边都带上去；所以返回 1 + max(左高, 右高)。
分步图解
每个节点返回“向父节点延伸的一条最长链”的高度；直径在某个节点处由左右高度相加得到。
后序求高度，同时更新直径
自拟树的最长路径完全在左子树内部：1 → 2 → 4 → 6 → 7，共 4 条边。经过根 8 的路径只有 1 + 3 条边，并不是答案。
图解
后序求高度，同时更新直径
普通节点已确认 / 结果
这是后序遍历：左右子树的高度先回来，当前节点才能更新 best。时间 O(n)，递归深度 O(h)。
时间 O(n)空间 O(h)
易错点
- 把直径定义成节点数：本题要求边数，左右高度相加即可，不再加 1。
- 返回 left + right 给父节点：父节点只能延续一条链，会把分叉重复计算。
- 只在根节点算一次 left + right：最长路径可能完全在子树内部。
对照解法
对每个节点求高度
枚举每个拐点，分别求左右高度
思路最直白，但每个节点都重复向下求高度，最坏 O(n²)；仅作对照。
对每个节点，分别求它左右子树的高度，相加得到“经过该节点的最长路径”；再递归检查左右子树内部。
正确性没有疑问，但高度函数会被反复调用：链状树上每个节点都向下扫一遍，退化到 O(n²)。
它的价值在于帮助理解“路径的拐点”这个概念；一旦想清楚，就可以用后序把高度缓存下来，降到 O(n)。
- 1空树返回 0。
- 2求左右子树高度，相加得到经过根的路径。
- 3递归求左右子树内部的直径。
- 4三者取最大。
时间 O(n²)空间 O(h)
易错点
- 忘记比较子树内部的直径：只算了经过根的路径。
- 高度定义成边数/节点数混用，最后差 1。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
演示输入
root = [8,4,12,2,6,null,null,1,null,null,7]每个节点返回“向父节点延伸的一条最长链”的高度；直径在某个节点处由左右高度相加得到。
后序求高度，同时更新直径
查看 C++ 代码
延伸阅读
- “路径在某个节点拐弯”是树形 DP 的常见视角；返回值只保留对父节点有用的一部分信息。
- 类似题：二叉树最大路径和（124）也是后序返回单边贡献，同时更新全局最优。