/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 递归
    // 递归检查左子树 是否包含节点 p 或 q。
    // 递归检查右子树 是否包含节点 p 或 q。
    // 如果当前节点自身是 p 或 q 中的一个，且其左子树或右子树包含另一个节点，那么该节点就是最近的公共祖先。
    // 如果当前节点的左右子树各包含一个目标节点（p 和 q），那么当前节点就是最近的公共祖先。
    // 如果上述情况都不成立，返回找到的包含目标节点的子树（可能为空，表示当前子树不包含目标节点）。
    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 && right != null) {//都不为空，说明公共祖先在根节点
            return root;
        }else if (left != null && right == null) { //一边为空，一边不为空，说明在公共祖先在不为空的一边
            return left;
        }else if (left == null && right != null) {
            return right;
        }
        return null;
    }
}