首页 > 代码库 > Lowest Common Ancestor of a Binary Search Tree

Lowest Common Ancestor of a Binary Search Tree

      3
       /           5         1
   /    \      /     6       2   0    8
         /           7   4

如上图所示,5和1的祖先是3,5和4的祖先是5;6和4的祖先是5;
 1 public class Solution {
 2     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 3         if(root == null) return null;
 4         if(root ==p || root == q) //如果root是结点p或者q,返回结点p或者q;
 5             return root;
 6         TreeNode l = lowestCommonAncestor(root.left,p,q); //返回null,说明节点p和节点q都不在root.left分支;如果l!= null,至少有一个结点在左分支
 7         TreeNode r = lowestCommonAncestor(root.right,p,q);//如果r!=null,至少有一个节点在右分支上
 8         if(l == null)
 9             return r;
10         if(r == null)
11             return l;
12             
13         return root;
14         
15     }
16 }

 2. Lowest Common Ancestor of a Binary Search Tree

 

     _______6______
       /                  ___2__          ___8__
   /      \        /         0      _4       7       9
         /           3   5
代码如下:
1 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
2         while((root.val-p.val)*(root.val-q.val)>0){
3             root = root.val>p.val?root.left:root.right;
4         }     //就一直找到第一个root使得(root.val-p.val)*(root.val-q.val)<=0 为止
5 return root; 6 }

 



 

Lowest Common Ancestor of a Binary Search Tree