LC235
二叉搜索树的最近公共祖先
BST · LCA可视化:树与递归栈BST 中 p=2,q=8 的最近公共祖先。
时间 O(n)空间 O(1)
题目1 / 14
题目与输入建立输入、目标与算法心智
找 2 与 8 的最近公共祖先
正在加载算法场景...
当前发生了什么
BST 中 p=2,q=8 的最近公共祖先。
机器状态
root、p、q 比较。
为什么正确
利用 BST:若 p,q 在 root 两侧则 root 是 LCA;否则往同侧走。
不变量
BST 性质决定 LCA 在两侧或同侧。
面试怎么说
while: p<root<q 或反向则 return root;否则往较小侧走。
人类输入
BST 中 p=2,q=8 的最近公共祖先。
机制
利用 BST:若 p,q 在 root 两侧则 root 是 LCA;否则往同侧走。
机器状态
root、p、q 比较。
可观察结果
LCA=6。
不变量
- · BST 性质决定 LCA 在两侧或同侧。
常见误区
- · 普通 LCA 也可但 BST O(h) 更简。
迁移练习
- · LC236 二叉树 LCA
- · LC700 搜索
面试怎么答
while: p<root<q 或反向则 return root;否则往较小侧走。