The lowest common ancestor (LCA) of two nodes is the deepest node that has both of them as descendants (a node is a descendant of itself). The tree is a general binary tree with no ordering guarantee, so you must search it. Given two distinct values a and b that both appear in the tree, output the value of their LCA.
Input format
One line: the binary tree as a level-order array.
The tree is encoded on ONE line as a space-separated level-order (breadth-first) array. The token null marks a missing child; the children of a null are omitted from the array. An empty tree is written as the single token null.
The next line: two space-separated integers a and b, the values of the two query nodes.
Output format
A single integer: the value stored at the lowest common ancestor of the two query nodes.
Constraints
- The tree has between 2 and 1000 nodes.
- All node values are distinct integers with absolute value at most 1000000.
- a and b are different values, and both are guaranteed to appear in the tree.