NeetCode #419LC-236MediumTrees
← Back to All Problems#419 · #236 · Lowest Common Ancestor of a Binary Tree(二叉树的最近公共祖先)
📌 Problem Statement & Constraints
Given a binary tree and two nodes
p and q, return their lowest common ancestor: the deepest node that has both as descendants (a node may be a descendant of itself). Constraints: the number of nodes is in [2, 10^5], all values are distinct, both nodes exist.💡 Core Algorithmic Approaches
- Recurse bottom-up. If the current node is
porq, return it immediately -- the answer is at or above this point. - Otherwise recurse into both children.
- If both children return a non-null result,
pandqlie in different subtrees, so the current node is the LCA. - If only one side is non-null, propagate it upward; that side already contains both nodes (or the LCA).
💻 Benchmark Python3 Implementation
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or root is p or root is q:
return root # found one of the targets, or a leaf
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root # p and q split here -> this is the LCA
return left or right # both are on one side
# Parent-pointer variant, if each node has a `parent` attribute
class Solution2:
def lowestCommonAncestor(self, p: "Node", q: "Node") -> "Node":
a, b = p, q
while a is not b:
a = a.parent if a.parent else q # switch to the other chain at the top
b = b.parent if b.parent else p
return a⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) for the tree version, O(h) for the parent-pointer version.
💾 Space Complexity
O(h) for the recursion stack; O(1) for the parent-pointer version.
⚠️ Interview Pitfalls & Follow-ups
- Comparing values instead of node identity:
root is pis required, since values are unique but identity is the direct test. - Returning as soon as one side is non-null without checking the other: both children must be examined to detect the split.
- Assuming
pandqare never ancestors of each other: the early return handles that case correctly. - Using the BST-specific algorithm: this tree has no ordering, so the general recursion is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.