Solution to Lowest Common Ancestor from Jobdu

14 Sep

Question (in Chinese):

Question Name: Lowest Common Ancestor

Question Description: Find the lowest common ancestor of two nodes in a binary tree.

Input: the input might contain multiple test cases. Globally the first line includes one interger N (0 <= N <= 1000). N is the number of test cases. The following 2*N lines contains one test case in each two lines. The first line of each test case is a list of integers, as the pre-order traversal result of a binary tree. 0 means the corresponding left/right subtree does not exist. The second line is two integers, as the value of two nodes (may not exist).

Output: print the value of the lowest common ancestor, if exist. Otherwise, print “My God”.

The solution is quite complicated if we need a really good performance. But here we are using a simple solution.

Leave a Reply

Your email address will not be published. Required fields are marked *