题目重点：直径按边数计算，允许不经过根，后序保存单臂高度并组合左右路径。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练每条边长度1，距离按边数，不是节点数或节点值之和；任意节点可为端点。
- 空树和单节点距离0，输入无环无共享子节点；示例按身份检查非法结构。
- 只返回距离；若需要端点/路径需额外保存最深后继。
解题路线
- 定义height(node)为从node向下最深路径的节点数，空子树0。单节点height=1，这样经过node的左右端点距离恰为height(left)+height(right)。
- 每个节点的直径候选可同时连接左右最深臂，但给父节点的height只能选一边：1+max(left,right)。与最大路径和一样，不能把双臂候选当单臂上传。
- 任意简单路径都有唯一最高节点，在它左右子树两端或以它为端点；遍历所有node候选取最大能覆盖全树，不要求最远路径经过根。
- 后序保证孩子height已经算好。显式stack以进入/退出标记实现，退出时聚合；节点身份seen检测重复访问，不按value去重。
- 为什么候选单位是边：左子树height=l时从node到左最深端点有l条边，右侧有r条，合起来l+r；单节点左右0，距离0。换成height按边定义则需要另外加2与空树特殊处理。
- 只求值时无需每个节点存完整路径。返回端点可记录每个height对应最深节点并在最佳候选保存两端，最后沿父关系构造一次；复制所有路径会在链状树变平方时间。
手动走一遍
根只有左子树，但左孩子左右各有长链，直径可以完全在左子树中，不能只算根的左右高。三节点链height根3，直径2；值可为负或重复，因为距离只由边决定。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from dataclasses import dataclass
@dataclass(eq=False)
class Node:
value: object
left: object = None
right: object = None
def diameter(root):
if root is None:
return 0
stack, seen, heights = [(root, False)], set(), {}
best = 0
while stack:
node, exiting = stack.pop()
if exiting:
left = heights.get(node.left, 0)
right = heights.get(node.right, 0)
best = max(best, left + right)
heights[node] = 1 + max(left, right)
else:
if node in seen:
raise ValueError('expected a tree')
seen.add(node)
stack.append((node, True))
if node.right is not None:
stack.append((node.right, False))
if node.left is not None:
stack.append((node.left, False))
return best
复杂度
O(n)时间，本显式栈、seen与height字典O(n)空间。保证树的纯递归求值版可只用O(h)栈，但最坏h=n；不要把本实现宣称O(log n)空间。
易错点与追问
容易失分的边界
- 只在根处算直径。
- 节点数和边数混淆。
- 上传左右高度之和导致分叉。
- 重复值当同一节点。
继续深挖
- 如何输出最远两端和路径？
- 带权边甚至负权时状态怎样改？
- 普通无向树两次BFS与此解法有何关系？
- 树结构动态变化如何维护直径？
