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

如上图给定的二叉树，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; 
    }
}