⚡Flashcard Drill➔
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

  1. In a BST, the LCA is the first node whose value lies between p.val and q.val (inclusive).
  2. Start at the root: if both values are smaller, go left; if both are larger, go right.
  3. Otherwise the current node splits the two, so it is the LCA.
  4. 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 p and q are always in different subtrees: one may be an ancestor of the other, in which case the ancestor is the LCA -- and the else branch 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.
🎯 Drill This Card Now➔

🧩 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 的有序性。
  • 条件用 &lt;= 而非 &lt; :题目保证所有值互不相同,用 &lt; 或 &lt;= 结果相同,但 &lt; 语义更准确。
  • 忘记「其中之一就是当前节点」的情况 :此时 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