NeetCode #421LC-235MediumTreesBlind 75NC 150NC 250
← Back to All Problems#421 · #235 · Lowest Common Ancestor of a Binary Search Tree(二叉搜索树的最近公共祖先)
📌 Problem Statement & Constraints
Given a binary search tree and two nodes
p and q, return their lowest common ancestor (LCA). Constraints: the number of nodes is in [2, 10^5]; all values are distinct; both nodes exist in the tree.💡 Core Algorithmic Approaches
- In a BST, the LCA is the first node whose value lies between
p.valandq.val(inclusive). - Start at the root: if both values are smaller, go left; if both are larger, go right.
- Otherwise the current node splits the two, so it is the LCA.
- The iterative form is O(1) space and avoids recursion entirely.
💻 Benchmark Python3 Implementation
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
cur = root
while cur:
if p.val < cur.val and q.val < cur.val:
cur = cur.left # both in the left subtree
elif p.val > cur.val and q.val > cur.val:
cur = cur.right # both in the right subtree
else:
return cur # the split point -> LCA
return None
# Recursive variant
class Solution2:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
return root⚡ Complexity Deep Dive
⏱️ Time Complexity
O(h): the search descends one level at a time, where h is the tree height.
💾 Space Complexity
O(1) for the iterative version; O(h) for the recursion.
⚠️ Interview Pitfalls & Follow-ups
- Using the general binary-tree LCA algorithm: it works but is O(n) instead of O(h); the BST ordering is what makes the fast version possible.
- Comparing with
<=on one side and<on the other inconsistently: since values are distinct, either strict form works, but be consistent. - Returning the child instead of the current node: the LCA is the node where the paths diverge, which is the current node.
- Assuming
pandqare always in different subtrees: one may be an ancestor of the other, in which case the ancestor is the LCA -- and theelsebranch returns it correctly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Trees Problems
中文速览与面试要点
二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:「对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。」约束:树中节点数在范围 [2, 10^5] 内;-10^9 ≤ Node.val ≤ 10^9;所有 Node.val 互不相同;p != q;p 和 q 均存在于给定的二叉搜索树中。
核心要点
- 利用 BST 的有序性(标准解) :从根开始,若 p、q 的值都小于当前节点,则 LCA 在左子树;都大于则 LCA 在右子树;否则当前节点就是「分叉点」,即 LCA。
- 为什么「分叉点」就是 LCA :p 与 q 分别位于当前节点的两侧(或其中之一就是当前节点),说明它们在这一节点首次「分开」,因此当前节点是最近的公共祖先。
- 迭代实现 :无需递归,用 while 循环沿路径下行即可,空间 O(1)。
- 对比 236(普通二叉树) :普通二叉树没有有序性,必须用后序遍历自底向上找,O(n) 而非 O(h)。
常见陷阱
- 用 236 的通用解法 :虽然也能得到正确答案,但 O(n) 而非 O(h),未利用 BST 的有序性。
- 条件用 <= 而非 < :题目保证所有值互不相同,用 < 或 <= 结果相同,但 < 语义更准确。
- 忘记「其中之一就是当前节点」的情况 :此时 else 分支会正确返回当前节点。
- 递归实现但树退化成链 :递归深度 O(n) 可能栈溢出。迭代版本更安全。
参考实现
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
cur = root
while cur:
if p.val < cur.val and q.val < cur.val:
cur = cur.left # 都在左子树
elif p.val > cur.val and q.val > cur.val:
cur = cur.right # 都在右子树
else:
return cur # 分叉点 -> 即 LCA
return None