思路:

• 根据函数的含义:p和q的最近公共祖先
• 找到所有情况然后进行递归
• 1.如果p和q分别在root的左右子树中，返回root
• 2.如果该节点的子树中只包含p,那么就返回p
• 3.如果该节点的子树中只包含q,那么就返回q

• 4.如果都不包含则返回null

• 如果递归时发现有一边返回了null

• 那么答案一定在另外一边，就返回另一边

/**
 * 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) {
        if(root == null || root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        if(left == null) return right;
        if(right == null) return left;
        return root;
    }
}