首页 > 代码库 > Lowest Common Ancestor of Two Nodes in a Binary Tree

Lowest Common Ancestor of Two Nodes in a Binary Tree

2024-08-06 01:18:48   218人阅读

Reference：

http://blog.csdn.net/v_july_v/article/details/18312089 

http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-ii.html

(1) Is the tree a BST or not?

     BST的话，我们就能按照BST的定义思考了。当前遍历的node如果比我们要找的两个点都大，说明那两个点都在当前node的左边，所以这两个node的祖先肯定在当前node的左边，所以往左边找。反之，往右边找。如果这两个点一个大于当前node一个小于当前node，说明当前node就是LCA。 如果这两个点一个是另一个的祖先，那么这个点就是LCA。

代码如下：

 1    public int query(Node t, Node u, Node v){
 2           int left = u.val;
 3        int right = v.val;
 4        Node parent = null;
 5        
 6        if(left > right){
 7            int temp = left;
 8            left = right;
 9            right = temp;
10        }
11        
12        while(true){
13            //t is smaller than u, v, then search in right tree
14            if(t.val < left){
15                prarent = t;
16                t = t.right;
17            }else if(t,val > right){
18                parent = t;
19                t = t.left;
20            }else if(t.val == left || t.val == right){
21                return parent.val;
22            }else{
23                return t.val;
24            }
25        }
26    }

 

（2）那如果不是BST呢？一般Binary Tree.

   a. Tree结构中没有parent域。

       递归找。

       代码如下：

      

 1 //Worst case O(n)
 2 Node getLCA(Node root, Node node1, Node node2){
 3         if(root == null)
 4             return null
 5         if(root == node1 || root == node2)
 6             return root;
 7         
 8         Node left = getLCA(root.left, node1, node2);
 9         Node right = getLCA(root.right, node1, node2);
10         
11         if(left != null && right != null)
12             return root;
13         else if(left != null)
14             return left;
15         else if(right != null)
16             return right;
17         else
18             return null;
19     }

 

 b. 如果有parent域。

    转化为两个linkedlist的交点问题。

    代码如下：

   

 1 int getHeight(Node p){
 2         int height = 0;
 3         while(p!=null){
 4             height++;
 5             p = p.parent;
 6         }
 7         return height;
 8     }
 9     
10     void swap(int a, int b){
11         a = a + b;
12         b = a - b;
13         a = a - b;
14     }
15     
16     Node getLCA(Node p, Node q){
17         int h1 = getHeight(p);
18         int h2 = getHeight(q);
19         
20         //q is always deeper than p
21         if(h1 > h2){
22             swap(h1, h2);
23             swap(p, q);
24         }
25         
26         int diff = h2 - h1;
27         
28         for( int i = 0; i < diff; i++)
29             q = q.parent;
30         
31         while(p!=null && q!=null){
32             //common node
33             if(p == q)
34                 return p;
35             p = p.parent;
36             q = q.parent;
37         }
38         
39         return NULL; //p and q are not in the same tree
40     }

Lowest Common Ancestor of Two Nodes in a Binary Tree


联系
我们