LC543
二叉树的直径
二叉树 · 直径可视化:树与递归栈直径=最长路径边数,可能不过根。
时间 O(n)空间 O(1)
题目1 / 10
题目与输入建立输入、目标与算法心智
空结点高度 0
正在加载算法场景...
当前发生了什么
直径=最长路径边数,可能不过根。
机器状态
depth、diameter global。
为什么正确
后序:depth=max(L,R);diameter=max(d, L+R)。
不变量
L+R 是经过根的直径候选。
面试怎么说
后序更新 global O(n)。
人类输入
直径=最长路径边数,可能不过根。
机制
后序:depth=max(L,R);diameter=max(d, L+R)。
机器状态
depth、diameter global。
可观察结果
直径边数。
不变量
- · L+R 是经过根的直径候选。
常见误区
- · 返回值仍是深度不是直径。
迁移练习
- · LC124 最大路径
- · LC687
面试怎么答
后序更新 global O(n)。