DIY: Lowest Common Ancestor of a Binary Tree III

Problem statement

Suppose you are given two nodes of a binary tree node1 and node2. Your task is to find the lowest common ancestor (LCA) of these two nodes in the tree.

Note: The lowest node that has both node1 and node2 as its descendants (where we allow a node to be a descendant of itself), is called the lowest common ancestor (LCA) of these two nodes.

For this problem, you can assume that the values of all the nodes are positive and unique and node1 != node2. Moreover, each node will have a reference to its parent node. The definition of Node can be viewed in the code widget below.

Note: The tree in the following test cases will be displayed in the form of an array representing the level-order traversal of the corresponding binary tree. For any missing nodes, there will be a -1 in the array.

Input

The input will be two nodes of a binary tree, node1 and node2. The following are examples of input to the function:

// Sample Input 1:
           3
         /    \
        /      \
       5        1
     /   \    /   \
    6     2  0     8
         /  \
        7    4

root = [3,5,1,6,2,0,8,-1,-1,7,4], node1 = 5, node2 = 1

// Sample Input 2:
         1
        /      
       2        

root = [1,2], node1 = 1, node2 = 2

Output

The output will a node that is the lowest common ancestor (LCA) of node1 and node2. The following are examples of the outputs:

// Sample Output 1:
3

// Sample Output 2:
1