二叉树的最近公共祖先 LCA
哪些公司问过
答案要点
- 后序递归:root 为空或等于 p、q,直接返回 root
- 左右子树返回值都非空:当前节点就是 LCA
- 只有一侧非空:把该侧结果向上传递;都为空则返回空
- 时间 O(n),空间 O(h)(递归栈深度)
- BST 可利用有序性:从根往下走,找到第一个值在 [p, q] 之间的节点
易错点
- 假设 p 和 q 一定在树里却没有说明
- 遇到 p 或 q 后继续往下递归
- BST 的做法没有利用有序性
- 把空间复杂度说成 O(1)
面试官常见追问
- 这个解法为什么是后序遍历?
- 如果节点 p 本身是 q 的祖先怎么办?
- 如果树的节点有父指针怎么做?
- 非递归怎么做?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场
- 二叉树的右视图7 场