TreeDFS
The lowest common ancestor (LCA) of two nodes p and q is the deepest node that has both of them as descendants (a node counts as a descendant of itself). Find it in a binary tree. Build the tree from the level-order input yourself, then solve the problem.
Input
Line 1: the tree in level order with null for missing children. Line 2: the values p and q. All node values are distinct, and both p and q exist in the tree.
Output
Print the value of the lowest common ancestor.
Constraints
2 <= number of nodes <= 2000
Example 1
Input
3 5 1 6 2 0 8 null null 7 4 5 1
Output
3
5 and 1 are on opposite sides of 3.
Example 2
Input
3 5 1 6 2 0 8 null null 7 4 5 4
Output
5
4 is a descendant of 5, so 5 is the LCA.