NC191 二叉搜索树的最近公共祖先

描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围:
3<=节点总数<=10000
0<=节点值<=10000

如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5}，如下图:

示例1
输入：{7,1,12,0,4,11,14,#,#,3,5},1,12
返回值：7
说明：
节点1 和 节点12的最近公共祖先是7   

示例2
输入：{7,1,12,0,4,11,14,#,#,3,5},12,11
返回值：12
说明：
因为一个节点也可以是它自己的祖先.所以输出12   
1
2
3
4
5
6
7
8
9
10
11

牛客网
搜索时将每个祖先存起来，然后再找相同值。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        ArrayList<Integer> res = new ArrayList<>();
        ArrayList<Integer> res1 = new ArrayList<>();
        TreeNode s = root;
        while(s != null){
            res.add(s.val);
            if(s.val < p){
                s = s.right;
            }else if(s.val>p){
                s = s.left;
            }else break;
        }
         while(root != null){
            res1.add(root.val);
            if(root.val < q){
                root = root.right;
            }else if(root.val>q){
                root = root.left;
            }else break;
        }
        // int strLen = Math.min(res.size(),res1.size());
        // int i = strLen-1;
        // while(i>=0 && res.get(i)!= res1.get(i)){i--;}
        // return i>=0?res.get(i):0;
         int result = 0;
        //比较两个路径，找到第一个不同的点
        for(int i = 0; i < res.size() && i < res1.size(); i++){
            int x = res.get(i);
            int y = res1.get(i);
            //最后一个相同的节点就是最近公共祖先
            if(x == y)
                result = res.get(i);
            else
                break;
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

思考：不理解为什么这段代码会出现错误。从最后开始查找，最先查到到的视为最近的

   // int strLen = Math.min(res.size(),res1.size());
        // int i = strLen-1;
        // while(i>=0 && res.get(i)!= res1.get(i)){i--;}
        // return i>=0?res.get(i):0;
1
2
3
4

递归：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        if(root == null) return -1;
        if((p>=root.val && q<=root.val) || (p<=root.val && q>=root.val)) return root.val;
        else if(p<=root.val && q<=root.val) return lowestCommonAncestor(root.left,p,q);
        else return lowestCommonAncestor(root.right,p,q);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31