leetcode-235二叉搜索树的最近公共祖先

原始思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return findAncestor(root, p, q);
    }
    public static TreeNode findAncestor(TreeNode root, TreeNode p, TreeNode q){
        //如果p,q分散在两边,那中间的肯定是共公祖先,当p、q其中一个为root的话,那么必然自己就是祖先
        if(p.val > root.val && q.val< root.val
            || p.val < root.val && q.val> root.val
            || p.val == root.val
            || q.val == root.val){
                return root;
            }
        
        //此时说明p、q必定分布在一边,选取任意一个值判断在左边还是右边,然后进行递归
        if(root.val > p.val){
            return findAncestor(root.left, p , q);
        }else{
            return findAncestor(root.right, p , q);
        }
    }
}