Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous post:Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.

Solution 1:
We can use a bottom-up approach. Find the first occurrence of two nodes from left sub-tree and right sub-tree respectively. Check whether these two occurrence lie on two different branches. If it is the case, return the root. Other wise, the first occurrence of the nodes must be either on the left branch or on the right branch. At this time, we already found the the ancestor node in one of the sub-tree, then we just return it.

Java语言: LCA

01 public TreeNode LCA(TreeNode root,TreeNode p, TreeNode q)

02 {

03     //base cases

04     if(root==null)

05         return null;

06     if(root==p || root==q)

07         return root;

08     TreeNode left=LCA(root.left,p,q);

09     TreeNode right=LCA(root.right,p,q);

10     //p and q are on the different branches, return root

11     if(left!=null && right!=null)

12         return root;

13     //p and q are on the same branch

14     else if(left!=null)

15         return left;

16     else

17         return right;

18 }

Solution 2:

As some of us may imagine, if we have a parent node of each node, then the question becomes very easy, we just check whether two nodes can be the same when they are climbing up from their parents to the root. If there is no such parent pointer, we can also construct the parent pointer ourselves. How? We can use hash tables! We do a pre-order (DFS) traversal, and in this process we keep inserting child->parent pairs into the hash table. Then we are able to climb up. In addition, we use another hash table to keep the depth of each node, the purpose of this is that this can make our process easy. We always climb up from the node at the lower level, until they reach the same level. If then they are still not equal, we just make them climbing up together, until they meet at somewhere.

Java语言: LCA2

01 public TreeNode LCA2(TreeNode root,TreeNode p, TreeNode q)
02 {
03     //handle special cases first
04     if(root==null)
05         return null;
06     if(root==p||root==q)
07         return root;
08     Hashtable<TreeNode,TreeNode> parents=new Hashtable<TreeNode,TreeNode>();
09     Hashtable<TreeNode, Integer> levels=new Hashtable<TreeNode,Integer>();      
10     //parents.put(root, null);
11     levels.put(root, 1);
12   
13     //DFS(preorder) the tree, after that the parents and levels are assigned
14     DFS(root,parents,levels);
15     int level_p=levels.get(p);
16     int level_q=levels.get(q);
17     while(level_p<level_q)
18     {
19         q=parents.get(q);
20         level_q--;
21     }
22     while(level_p>level_q)
23     {
24         p=parents.get(p);
25         level_p--;
26     }
27     while(p!=q)
28     {
29         p=parents.get(p);
30         q=parents.get(q);
31     }
32     return p;
33 }
34 
35 public void DFS (TreeNode node, Hashtable<TreeNode,TreeNode> parents,Hashtable<TreeNode, Integer> levels)
36 {
37     int level=levels.get(node);
38     if(node.left!=null)
39     {
40         parents.put(node.left, node);
41         levels.put(node.left, level+1);
42         DFS(node.left,parents,levels);
43     }
44     if(node.right!=null)
45     {
46         parents.put(node.right,node);
47         levels.put(node.right, level+1);
48         DFS(node.right,parents,levels);
49     }
50 }