346. Lowest Common Ancestor
Print the value of the deepest node that has BOTH the node holding value a
and the node holding value b somewhere beneath it. A node counts as its own
descendant, so if a sits above b, the answer is a.
4
/ \
2 6 lca(1, 3) is 2
/ \ / \ lca(1, 7) is 4
1 3 5 7 lca(4, 1) is 4, since 4 is an ancestor of itself
The recursive form is short once stated properly. Ask each subtree whether it
contains a or b. If the two answers come back from DIFFERENT children, this
node is the meeting point. If they both come from the same child, the answer is
further down. And a node that itself holds a or b reports itself
immediately.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - All values are distinct, and both `a` and `b` appear in the tree. - The input always forms a valid tree rooted at node 1.
Input
The first line contains three integers n, a and b.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains the left and right child of node i,
using 0 for no child. Node 1 is the root.
Output
Print one integer, the value at the lowest common ancestor.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.