476. Shared Ancestor
A family tree of a village is stored as a binary tree: the founder is root and each person has at most a left and a right child. Two villagers p and q are picked, and the elders want to find their closest shared ancestor: among all villagers who have both p and q somewhere in their own subtree, pick the one that is deepest in the tree. A villager counts as being in his or her own subtree, so p itself can be the answer when q is below it.
Return the node that is the closest shared ancestor of p and q. Both nodes are guaranteed to be present in the tree, and p and q may be the same node.
Example 1
- Input:
- root = [14,6,22,3,9,18,30,null,null,7,12]p = {"nodeOf":0,"val":7}q = {"nodeOf":0,"val":12}
- Output:
- 4
- Explanation:
Nodes 7 and 12 are the two children of node 9, which is their closest shared ancestor.
Example 2
- Input:
- root = [14,6,22,3,9,18,30,null,null,7,12]p = {"nodeOf":0,"val":3}q = {"nodeOf":0,"val":18}
- Output:
- 0
- Explanation:
Nodes 3 and 18 sit in different subtrees of the root, so the root 14 is the answer.
Example 3
- Input:
- root = [14,6,22,3,9,18,30,null,null,7,12]p = {"nodeOf":0,"val":9}q = {"nodeOf":0,"val":7}
- Output:
- 4
- Explanation:
Node 7 lies below node 9, and a node counts as its own ancestor, so the answer is 9.
Constraints
1 ≤ number of nodes ≤ 5000
-104 ≤ Node.val ≤ 104
All node values are distinct.
p and q are nodes of the tree.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)