二叉树的公共祖先

普通二叉树的公共祖先

只能通过深度遍历来找。

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
         return CommonAncestor(root,o1,o2).val;

    }
    public TreeNode CommonAncestor(TreeNode root, int o1, int o2) {
        //直接返回
        if(root == null || root.val == o1 || root.val == o2){
            return root;
        }
        TreeNode left = CommonAncestor(root.left, o1, o2);
        TreeNode right = CommonAncestor(root.right, o1, o2);
        //如果不是根节点，在右子树，还是会递归返回到根节点这，直接返回右子树
        if(left == null) return right;
        //同理
        if(right == null) return left;
        return root;
    }
}

二叉搜索树的公共祖先

可以借助二叉树的性质，我们先把二叉搜索树查找的框架写出来：

public BST(TreeNode root, int target){
    if(root == null)
        return null;
    if(root.val == target){
        //找到后做点什么
    }else if(root. val < target){
        BST(root.right, target);
    }else if(root.val > target){
        BST(root.left, target);
    }
}

因为我们找到是公共祖先，而且有两个参数，所以修改一下：

public class Solution{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root.val > p.val && root.val > q.val){
            lowestCommonAncestor(root.left, p, q);
        }else if(root.val < p.val && root.val < q.val){
            lowestCommonAncestor(root.right, p, q);
        }else{
            return root;
        }
    }
}

其实这道题也可以用迭代来做：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null){
            if(root.val < p.val && root.val < q.val){
                root = root.right;  
            }else if(root.val > p.val && root.val > q.val){
                root = root.left;
            }else{
                break;
            }
        }
        return root;
    }
}