LC236
二叉树的最近公共祖先
二叉树 · LCA可视化:树与递归栈普通二叉树求 p,q 最近公共祖先。
时间 O(n)空间 O(1)
题目1 / 14
题目与输入建立输入、目标与算法心智
找 5 与 1 的最近公共祖先
正在加载算法场景...
当前发生了什么
普通二叉树求 p,q 最近公共祖先。
机器状态
递归返回值语义。
为什么正确
后序:左右若均找到则 root;一侧找到则传上;都无 null。
不变量
返回结点表示该子树是否含 p 或 q 或 LCA。
面试怎么说
DFS 后序 O(n)。
人类输入
普通二叉树求 p,q 最近公共祖先。
机制
后序:左右若均找到则 root;一侧找到则传上;都无 null。
机器状态
递归返回值语义。
可观察结果
LCA 结点。
不变量
- · 返回结点表示该子树是否含 p 或 q 或 LCA。
常见误区
- · 必须后序才知道子树信息。
迁移练习
- · LC235 BST LCA
- · LC1676 四 LCA
面试怎么答
DFS 后序 O(n)。