Lowest common ancestor
You get the root of a binary tree and two different nodes of that tree, p and q. All values in the tree are different. An ancestor of a node is any node on the way from the root down to it, and a node counts as an ancestor of itself.
Return the lowest common ancestor of p and q: the node that is an ancestor of both and is farthest from the root. Return the node itself, not its value. If p is an ancestor of q, the answer is p.
Examples write a tree level by level, left to right, with None where a child is missing, and name p and q by their values.
root = [1, 2, 3, 4, 5, 6, None, None, None, 7, 8], p = 4, q = 8Outputthe node 24 is the left child of node 2, and 8 hangs below node 5 on the right of node 2. No lower node has both below it.
root = [1, 2, 3, 4, 5, 6, None, None, None, 7, 8], p = 7, q = 6Outputthe node 17 is on the root's left side and 6 is on its right side, so only the root has both.
root = [1, 2, 3, 4, 5, 6, None, None, None, 7, 8], p = 5, q = 8Outputthe node 58 is below 5, and 5 counts as its own ancestor.
2 ≤ number of nodes ≤ 2 × 105
The tree is at most 900 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
All values are different.
pandqare different nodes, and both are in the tree.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.