Given the root of a binary tree and two nodes p and q that are both in the tree, return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as an ancestor of itself. All values are unique. (In the tests, p and q are given by value and the judge passes the matching nodes.)
- The number of nodes is in the range 2 to 10^5
- -10^9 <= Node.val <= 10^9
- All values are unique, p != q, and both exist in the tree
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A brute force finds the root to p path and the root to q path, then walks both until they split. That is O(n) but needs two searches and extra lists. A single post-order DFS does better: each call returns p or q if it finds one in its subtree, and null otherwise. The first node where one target comes up from the left and the other from the right is exactly the lowest common ancestor. If a node is itself p or q, we can return it immediately, because if the other target lies below, this node is the answer anyway.
Algorithm
- If
rootis null, orrootisporq, returnroot. - Let
left = lca(root.left, p, q)andright = lca(root.right, p, q). - If both are non-null,
pandqare on different sides, so returnroot. - Otherwise return whichever of
leftandrightis non-null.
O(n)Space: O(h) recursion depthp alone.class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if root is None or root is p or root is q: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right: return root # p and q are on different sides return left if left else right