二叉树的最近公共祖先

题目描述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

二叉树 .png

示例：
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

Java代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //当越过叶节点，直接返回null；当root等于p或q，直接返回root
        if(root == null || root == p || root == q) return root;

        //开始递归左孩子，返回值记为left
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        //开始递归右孩子，返回值记为right
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        

        //当left和right同时为空时，说明root的左右孩子中都不包含p,q，此时返回null
        if(left == null && right == null) return null;
        //当left为空，right不为空时，p,q都不在root的左孩子中，直接返回right:
            //1.p,q其中一个在root的右孩子中，此时right指向p
            //2.p,q都在root的右孩子中，此时的right指向最近的公共祖先节点
        if(left == null) return right;
        //当right为空，left不为空时，p,q都不在root的右孩子中，直接返回left
        if(right == null) return left;

        //当left和right同时不为空，说明p,q分别位列root的两侧，因此root为最近公共祖先
        return root;
    }
}