二叉树中任意两个节点的最近公共祖先

2018-08-31  本文已影响0人  Katakuly
二叉树.jpg

如上图给定的二叉树,9和2的最近公共祖先是2;8和6的最近公共祖先是1。

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val){
        this.val=val;
    }
}

public class Solution{
    public TreeNode lowestCommonAncestor (TreeNode root,TreeNode node1,TreeNode node2){
        if (root==null || root==node1 || root==node2) {
            return root;
        }
        //采用递归调用的思路,将二叉树分为左子树和右子树分别处理
        //使用递归需要注意两点:
        //1.子问题需与原始问题为同样的问题,且更为简单;2.不能无限制地调用本身,程序必须有出口
        //查看左子树中是否有目标结点,没有为null
        TreeNode left = lowestCommonAncestor(root.left,node1,node2);
        //查看右子树是否有目标节点,没有为null
        TreeNode right = lowestCommonAncestor(root.right, node1, node2);
        //都不为空,说明做右子树都有目标结点,则公共祖先就是本身
        if((left==node1 && right==node2 ) || (left==node2 && right==node1)) { 
            return root;
        }
        return left==null?right:left; 
    }
}
上一篇下一篇

猜你喜欢

热点阅读