NeetCode #420LC-1650MediumTrees
← Back to All Problems#420 · #1650 · Lowest Common Ancestor of a Binary Tree III(二叉树的最近公共祖先 III)
📌 Problem Statement & Constraints
Given two nodes
p and q in a binary tree where each node has a parent pointer, return their lowest common ancestor. Constraints: the number of nodes is in [2, 10^5], all values are distinct.💡 Core Algorithmic Approaches
- With parent pointers, the problem is identical to finding the intersection of two singly linked lists.
- Advance both pointers one step at a time; when one reaches the top (its
parentisNone), redirect it to the other node. - After at most
depth(p) + depth(q)steps, both pointers have travelled the same total distance and meet at the LCA. - This needs no depth computation and uses O(1) space.
💻 Benchmark Python3 Implementation
class Solution:
def lowestCommonAncestor(self, p: "Node", q: "Node") -> "Node":
a, b = p, q
while a is not b:
# when a chain ends, continue along the other chain
a = a.parent if a.parent else q
b = b.parent if b.parent else p
return a⚡ Complexity Deep Dive
⏱️ Time Complexity
O(depth(p) + depth(q)): both pointers travel the combined path length.
💾 Space Complexity
O(1): two pointers.
⚠️ Interview Pitfalls & Follow-ups
- Not switching chains at the root: the pointers would simply reach
Noneand never meet. - Computing the depths and aligning the pointers: correct and O(1) space, but the chain-switching trick is shorter.
- Using a set of visited ancestors: O(h) space for the same result.
- Assuming the nodes are at the same depth: they need not be, which is exactly what the switching equalises.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.