二叉树的最近公共祖先（高频面试题）

题目链接

俩情况：

1. 在当前节点的两侧，最近公共祖先是当前节点。
2. 在当前节点的一侧，先找到的p或q是最近公共祖先。

俩情况对应的图：

在两侧 在一侧

代码书写顺序

上来先写：

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;

最后在最上面补上递归截止条件：

if (root == null) return null;
if (root == p || root == q) return root;

完整代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (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;
    }
}