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 TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

2         

if(p.val < root.val && q.val < root.val)

3             

return lowestCommonAncestor(root.left, p, q);

4         

else 

if(p.val > root.val && q.val > root.val)

5             

return lowestCommonAncestor(root.right, p, q);

6         

else

7             

return root;

8     } 

 

（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 

    }