LeetCode 剑指 Offer 68 - II. 二叉树的最近公共祖先

2022-09-26 HGNULB 约 9 分钟

文章信息 8 个分类 3 个标签

分类

LeetCode CodeTop 简单未解决 2-5 字节跳动剑指 Offer 剑指 Offer（第 2 版）

题目描述

✅ 剑指 Offer 68 - II. 二叉树的最近公共祖先

题意分析

给一棵普通二叉树和树中的两个节点 p、q，要找出「深度最大的、同时是这两个节点祖先的那个节点」。题目特意补了一句「一个节点也可以是它自己的祖先」，这句话把一整类边界收编了进来——如果 p 本身就在 q 的上方，答案就是 p 自己，而不是它的父节点。

要返回的是节点引用而不是节点值，说明结果必须是原树里那个真实存在的对象，不能新建节点。

约束信号有三条。第一，这是普通二叉树而非二叉搜索树，节点值不满足任何有序性，所以不能靠比较大小来决定往哪边走，只能老老实实两边都搜。第二，题目保证 p 和 q 都存在于树中，这条保证很关键，它允许一发现目标就提前返回而不必确认另一个也在，若换成不保证存在的变体，这个剪枝就会出错。第三，节点值互不相同，所以用值比较和用引用比较在本题等价，但写引用比较更稳。

边界要列全：p 和 q 分别在根的两侧；两者在同一侧；其中一个恰好是根；其中一个是另一个的祖先；以及递归过程中不断出现的空子树。

解法：递归后序遍历

核心思路

最容易想到的做法是先从根出发把到 p 的路径记下来，再记一遍到 q 的路径，然后从头比对两条路径，最后一个相同的节点就是答案。它是对的，但要两遍搜索加两个显式的路径容器，还得额外处理路径怎么回溯的问题。

瓶颈在于「路径」这个中间产物其实是多余的。真正需要的信息只有一条：对每棵子树而言，p 和 q 落在里面的是零个、一个还是两个。而这个信息完全可以从子树自底向上汇报上来，不需要显式记录路径。

于是把递归函数的返回值含义钉死，这就是本解法的不变量：lca(node) 返回值的含义是——若 node 的子树里同时含有 p 和 q，返回它们在该子树中的最近公共祖先；若只含其中一个，返回那一个；若一个都不含，返回 null。

有了这条不变量，父节点只需看两个孩子汇报上来的结果就能拼出自己的答案。左右都非空，说明 p 和 q 分居两侧，当前节点是唯一能同时覆盖它们的最深节点，返回自己；只有一侧非空，说明两个目标（或唯一找到的那个目标）都在这一侧，当前节点还不够深，把那一侧的结果原样上传；两侧都空则返回 null。三种情况恰好覆盖了不变量要求的全部语义，归纳成立。

递归的终止条件同样由不变量推出：空节点什么都不含，返回 null；碰到 node == p 或 node == q 就直接返回 node。后者看起来「偷懒」——万一另一个目标就藏在这棵子树更深处呢？但那种情况下当前节点本身就是最近公共祖先（因为一个节点可以是自己的祖先），返回它恰好正确。注意这一步依赖「两个节点都保证存在」的前提。

解题步骤

先写终止条件：root 为空、或等于 p、或等于 q 时，直接返回 root。为什么三种情况能合并成一行：空时该返回 null，而此时 root 就是 null；命中目标时该返回该节点，而此时 root 就是那个节点，返回值恰好都是 root。

递归求左子树的结果 left 和右子树的结果 right。为什么两边都必须求：普通二叉树没有有序性，无法预先判断目标在哪一侧；即使左边已经找到一个，也必须去右边确认另一个是否在那里。

若 left 和 right 都非空，返回当前节点。为什么它就是答案：两个目标分别位于左右子树，任何比当前节点更深的节点都只能待在其中一侧，覆盖不了另一侧，所以当前节点是深度最大的公共祖先。

若只有 left 非空，返回 left；否则返回 right（right 为空时返回的就是 null，语义自洽）。为什么原样上传：此时当前节点的另一侧没有任何目标，答案必然在非空的那一侧，且已经由那一侧按同样的不变量算好了。

整个判断写在两次递归调用之后，也就是后序位置。为什么必须后序：当前节点的结论完全依赖两个孩子的汇报，前序位置根本拿不到这些信息。

以官方样例 root = [3,5,1,6,2,0,8,null,null,7,4]、p = 5、q = 1 走一遍：这棵树的根是 3，左孩子 5（其左孩子 6，右孩子 2，2 的孩子是 7 和 4），右孩子 1（孩子是 0 和 8）。调用 lca(3)：3 既不是 p 也不是 q，继续递归。lca(5) 一进门就发现 root == p，直接返回节点 5，连 6 和 2 那两棵子树都不用进。lca(1) 同样一进门就命中 q，返回节点 1。回到节点 3，left = 5 非空、right = 1 非空，两个目标分居两侧，返回节点 3。答案是 3。

再看祖先关系的那组 p = 5、q = 4：lca(3) 不命中，先算左边。lca(5) 命中 p，立即返回节点 5——注意 4 其实就藏在 5 的子树里（5 → 2 → 4），但我们没有继续深入，这正是「节点可以是自己的祖先」允许的提前返回。再算右边，lca(1) 不命中，其左孩子 0 和右孩子 8 都不是目标且各自的孩子为空，逐层返回 null，所以 lca(1) 返回 null。回到节点 3，left = 5、right = null，只有一侧非空，把节点 5 原样上传。答案是 5，与预期一致。

代码实现

// 若左右都返回非空，当前节点即为 LCA。
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 && right != null) {
            return root;
        }
        if (left != null) {
            return left;
        }
        return right;
    }
}

// 若左右都返回非空，当前节点即为 LCA。
func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }

    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return right
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是节点总数。凭据：每个节点至多被访问一次，在它身上只做常数次比较和两次子调用的结果合并；命中目标时的提前返回只会让实际访问数更少，不会更多。

空间复杂度：$O(n)$，凭据：除递归调用栈外没有任何额外结构，栈深等于树高 $h$；平衡树时 $h=O(\log n)$，但退化成链状时 $h=n$，最坏情况下与节点数同阶。

关键点总结

写树上递归的第一件事是把返回值的含义用一句话写死，而不是先写代码再倒推。本题的「含两个就返回 LCA、含一个就返回那一个、都不含返回空」这句话一旦确定，终止条件和合并逻辑就是照抄出来的。

「自底向上汇报」能替掉一大类显式的路径记录。当父节点的答案只取决于孩子的汇总信息时，就该用后序遍历让信息自然回流，而不是自上而下维护栈或路径数组。

提前返回是有前提的。这里敢在命中 p 时立刻返回，靠的是题目保证两个节点都存在；换成不保证存在的变体（如需要同时确认两者都被找到），就必须去掉剪枝并额外统计命中个数。

分支的判断顺序不能乱：必须先判「两侧都非空」，再判单侧。反过来写会在两个目标分居两侧时提前把某一侧的目标当答案返回。

面试视角：几乎必然被追问「和二叉搜索树版本有什么区别」。标准回答是 BST 可以用值和根比较来决定往哪一侧走，单路下降到 $O(h)$；普通二叉树没有有序性，必须两侧都递归，所以是 $O(n)$。

面试视角：另一个高频追问是「如果要频繁查询多对节点怎么办」。此时不能每次都跑 $O(n)$，应答倍增法预处理祖先表做到单次 $O(\log n)$，或离线用 Tarjan 配并查集；能报出方向就够，不必现场写。

易错点总结

错误写法：把判断顺序写成先 if (left != null) return left; 再判两侧都非空。用例 p = 5、q = 1 分居根的两侧 → 左子树返回节点 5 后直接被上传，答案变成 5，而正确答案是根节点 3。

错误写法：为了「优化」，在 left 非空后就跳过右子树的递归。用例同样是 p、q 分居两侧 → 根本没去右边查看，永远得不到「两侧都非空」的信号，答案退化成先找到的那个节点。

错误写法：漏掉 root == null 的终止条件。用例任意含叶子节点的树 → 递归到叶子的空孩子时访问 root.left 直接空指针异常。

错误写法：只在两侧都非空时返回当前节点，其余情况一律返回 null。用例 p 是 q 的祖先，如 p = 5、q = 4 → 找到的目标信息无法向上传递，整棵树递归下来只得到 null。

错误写法：套用二叉搜索树的思路，比较 p.val、q.val 与 root.val 的大小来决定只走一侧。用例根为 3、左子树根为 5 → 按大小判断会认为 5 应该在右侧，一路走错，找不到目标；普通二叉树的节点值没有任何有序性。

错误写法：把判定写成 root.val == p.val，并在含有重复值的树上使用。用例存在两个值都为 5 的节点 → 会命中错误的那个节点并据此返回，答案指向了树中另一个位置；本题保证值唯一所以侥幸不出错，但引用比较才是通用写法。

错误写法：把判断挪到前序位置，先用某种条件判断当前节点是不是 LCA 再递归。用例任意树 → 当前节点的结论必须依赖两个孩子的汇报，前序位置这些信息还不存在，无法做出正确判断。

错误写法：直接照搬本解法去做「不保证 p、q 都在树中」的变体。用例 q 根本不在树里而 p 在 → 递归会在命中 p 时返回它，最终答案是 p，但正确答案应为空；这类变体必须去掉提前返回并显式统计找到了几个目标。

错误写法：改用「记录父指针 + 向上跳」的迭代解法时，只把 p 的祖先放进集合却忘了把 p 自己也放进去。用例 p 是 q 的祖先 → 从 q 往上跳会越过 p 找到 p 的父节点，答案偏浅了一层。

错误写法：返回新建的节点或返回节点值。用例任意输入 → 判题比对的是原树中的节点引用，返回值相同但对象不同会被判为错误答案。

相似题目

题目	难度	考察点
235. 二叉搜索树的最近公共祖先	中等	利用有序性单路下降，复杂度降到树高
236. 二叉树的最近公共祖先	中等	本题的主站原题，可直接对照代码
1644. 二叉树的最近公共祖先 II	中等	不保证节点存在，必须显式统计命中个数
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先	简单	同为搜索树版本，可练习迭代写法免掉递归栈
面试题 04.08. 首个共同祖先	中等	同一逻辑换皮，可对比父指针加集合的迭代解法