235. Lowest Common Ancestor of a Binary Search Tree

一、题目

　　1、审题

　　2、分析

　　　　给出一棵二叉查找树中的两个节点，求出这两个节点的最小共同祖先。

二、解答

　　1、思路

　　　　方法一、

　　　　　　当 p、q 中的一个是 root 节点时，或者 p、q 一个为root 左子树节点，一个为右子树节点，则 root 才是他们的共同最小祖先。

 1 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 2         
 3         // 必须是 p < q
 4         if(p.val > q.val) {
 5             TreeNode tmp = q;
 6             q = p;
 7             p = tmp;
 8         }
 9         while(root != null) {
10             if (root.val == p.val || root.val == q.val) 
11                 return root;
12             
13             boolean pInLeft = isChildren(root.left, p);
14             if(!pInLeft) { // p 不在左子树
15                 root = root.right;;
16                 continue;
17             }
18             
19             boolean qInRight = isChildren(root.right, q);
20             if(qInRight)    // q 在右子树
21                 return root;
22             
23             // q 不在右子树
24             root = root.left;
25         }
26         return null;
27     }
28     
29     private boolean isChildren(TreeNode root, TreeNode p) {
30         TreeNode node = root;
31         while(node != null) {
32             if(node.val == p.val)
33                 return true;
34             else if(node.val < p.val)
35                 node = node.right;
36             else 
37                 node = node.left;
38         }
39         return false;
40     }

　　方法二、

　　　　p、q一个为左孩子、一个为右孩子。即 p、q中一个值比 root 大，一个比 root 小；或者一个值为 root ，则返回 root 节点。采用数值计算

1     public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
2         // 当 p、q一个在左子树一个在右子树时才返回
3         while((root.val - p.val) * (root.val - q.val) > 0) 
4             root = p.val < root.val ? root.left : root.right;
5         return root;
6     }

　　方法三、

　　　　采用递归方法。

1     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
2         if(root.val > p.val && root.val > q.val)
3             return lowestCommonAncestor(root.left, p, q);
4         else if(root.val < p.val && root.val < q.val)
5             return lowestCommonAncestor(root.right, p, q);
6         else 
7             return root;
8     }