236. 二叉树的最近公共祖先

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 基本情况：如果根节点为空，或者根节点是p或q之一，则返回根节点
    if (root == null || root == p || root == q) {
        return root;
    }
    
    // 递归在左子树中查找
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    // 递归在右子树中查找
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    // 如果左子树中没有找到p或q，说明它们都在右子树中
    if (left == null) {
        return right;
    }
    // 如果右子树中没有找到p或q，说明它们都在左子树中
    if (right == null) {
        return left;
    }
    
    // 如果p和q分别在左右子树中，则当前根节点就是最近公共祖先
    return root;
}