【leetcode】（中等）236. 二叉树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //结束条件
        if(root == null) return root;
        //root即为最近公共祖先
        if(root == p || root == q) return root;
        //否则在左右树里寻找
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        //左右都不为空，即为root
        if(left != null && right != null) return root;
        //否则输出找到的最大公共祖先
        if(left == null) return right;
        if(right == null) return left;
        //如果左右都没有，root也不相等，就说明有节点也许不全都在树内
        return null;
    }
}