CS-Notes 剑指 Offer 68：树中两个节点的最低公共祖先（BST 235 与普通二叉树 236）详解

本文基于 CS-Notes 仓库中 [68. 树中两个节点的最低公共祖先](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/68. 树中两个节点的最低公共祖先.md?utm_source=gitcode_repo_files) 展开，系统讲解“最低公共祖先（Lowest Common Ancestor，LCA）”的两个经典变体：二叉查找树场景（对应 LeetCode 235）与普通二叉树场景（对应 LeetCode 236）。前者利用 BST 的大小序性质做单侧下降定位分裂点，后者使用后序递归自底向上聚合左右子树的查找结果。读完本篇，你可以完整掌握两种树上求 LCA 的解法代码、边界条件处理与复杂度分析，并能结合仓库中同系列题解进行交叉印证。

题目定位：LCA 是树形结构的经典考点

在 剑指 Offer 题解 - 目录 中，“68. 树中两个节点的最低公共祖先”被归入“树”专题，是该系列的压轴题之一，一题两问：

• 68.1 二叉查找树：树满足 BST 性质，可按值缩小搜索范围，对应 LeetCode 235（Easy）；
• 68.2 普通二叉树：无大小序约束，需要遍历两棵子树，对应 LeetCode 236（Medium）。

先明确 LCA 的定义：给定二叉树中的两个节点 p、q，它们的所有公共祖先里距离根节点最远的那一个，就是最低公共祖先。按题目约定，节点可以视为自己的后代——仓库中 Leetcode 题解 - 树 收录的两道题的样例说明均指出 “a node can be a descendant of itself according to the LCA definition”。因此当 p 恰好位于 q 的祖先路径上时，LCA 就是 p 本身，这一约定在两种解法的边界处理中都会体现。

68.1 二叉查找树变体（LeetCode 235）

解题思路：利用 BST 性质做单侧下降

原文档给出的核心判断条件是：两个节点 p、q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val（该写法以 p.val <= q.val 为前提）。代码中则采用了不依赖 p、q 相对顺序的等价判断，逻辑如下：

1. BST 的性质是：任意节点的左子树值都小于它，右子树值都大于它；
2. 从根节点向下搜索：若 root.val > p.val && root.val > q.val，说明 p、q 只可能都在左子树，继续左移；
3. 若 root.val < p.val && root.val < q.val，说明 p、q 只可能都在右子树，继续右移；
4. 两种情况都不满足时，p、q 在当前节点处“左右分裂”（或当前节点就是 p、q 之一），当前节点即最低公共祖先。

下图即 BST 中依据比较结果确定下降方向的过程示意：

参考代码

以下代码完整继承自 [原文档 68.1 小节](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/68. 树中两个节点的最低公共祖先.md?utm_source=gitcode_repo_files#L16-L26)：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null)
        return root;
    if (root.val > p.val && root.val > q.val)
        return lowestCommonAncestor(root.left, p, q);
    if (root.val < p.val && root.val < q.val)
        return lowestCommonAncestor(root.right, p, q);
    return root;
}

逐行说明：

• if (root == null) return root;：空节点保护。题目保证 p、q 一定在树中，因此搜索过程中只要未找到分裂点，递归不会走到空节点；
• 第一个 if：当前值同时大于 p、q，两者必然在左子树，把问题收敛为左子树上的同一子问题；
• 第二个 if：当前值同时小于 p、q，两者必然在右子树；
• 兜底的 return root;：既不是“都偏左”也不是“都偏右”，说明当前节点就是分裂点，直接返回。

由于每次递归只向一个孩子下降，该解法也可以改写为不需要递归栈的迭代形式（等价转换，便于面试时说明空间复杂度）：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (root.val > p.val && root.val > q.val)
            root = root.left;
        else if (root.val < p.val && root.val < q.val)
            root = root.right;
        else
            return root;
    }
    return null;
}

样例逐步推演

仓库 Leetcode 题解 - 树 中收录了 235 题的样例树：

        _______6______
      /                \
  ___2__             ___8__
 /      \           /      \
0        4         7        9
        /  \
       3   5

• p = 2，q = 8：根节点 6 不满足 6>2&&6>8，也不满足 6<2&&6<8，直接返回 6。LCA = 6，与样例描述 “LCA of nodes 2 and 8 is 6” 一致；
• p = 2，q = 4：6 同时大于 2、4，下降到左子树节点 2；在节点 2 处 2>2 不成立、2<2 也不成立，返回 2。LCA = 2，体现了“节点可以是自身后代”的约定（p 就是 q 的祖先）。

复杂度

• 时间复杂度 O(h)，h 为树高：每层最多访问一个节点，沿一条路径下降到分裂点；
• 空间复杂度 O(h)：递归调用栈的深度（迭代写法可降为 O(1)）；
• 最坏情况（树退化为链状）h = n，退化为 O(n)。

68.2 普通二叉树变体（LeetCode 236）

解题思路：后序递归聚合两棵子树的结果

原文档给出的思路是：在左右子树中查找是否存在 p 或者 q，如果 p 和 q 分别在两个子树中，那么就说明根节点就是最低公共祖先。由于普通二叉树没有大小序，无法像 68.1 那样单侧下降，必须把左右子树都查一遍，并用后序递归把结果“自底向上”汇总。递归函数的语义可以理解为：返回“本子树中找到的目标节点”——

1. 找到 p 或 q 之一：向上返回该节点；
2. p、q 分别出现在左、右子树：左右返回值都非空，当前节点就是 LCA；
3. p、q 都在同一侧子树：把非空的那一侧结果原样上抛；
4. 子树中一个目标都没找到：返回 null。

下图示意普通二叉树中后序递归的返回过程（子树未找到目标时返回 null）：

参考代码

以下代码完整继承自 [原文档 68.2 小节](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/68. 树中两个节点的最低公共祖先.md?utm_source=gitcode_repo_files#L41-L47)：

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);
    return left == null ? right : right == null ? left : root;
}

逐行说明：

• if (root == null || root == p || root == q) return root;：三种终止情况——空节点返回 null；当前节点本身就是 p 或 q 时直接返回该节点（返回 root 而非继续向下，正是“p 是 q 祖先”场景的正确性来源：递归从更深节点回到 p 时，另一侧会带回 q，三目判断最终把 p 作为答案上抛）；
• 中间两行：先序贯请求左右子树的查找结果；
• 最后的三目合并：左右都非空 → p、q 分裂在两侧，返回当前 root；只有单侧非空 → LCA 在那一侧，上抛该结果；两侧都为 null → 本子树不含任何目标，返回 null。

样例逐步推演

仓库 Leetcode 题解 - 树 中收录了 236 题的样例树：

       _______3______
      /              \
  ___5__           ___1__
 /      \         /      \
6        2       0        8
        /  \
       7    4

• p = 5，q = 1：左子树在节点 5 处命中基础条件返回 5；右子树在节点 1 处命中基础条件返回 1；根节点 3 收到 left = 5、right = 1，两侧非空，返回 3。LCA = 3，与样例描述 “LCA of nodes 5 and 1 is 3” 一致；
• p = 5，q = 4：节点 5 触发 root == p 基础条件，整个左子树的递归直接上抛 5（q = 4 在 5 的右子树中，不需要再深入）；节点 1 所在的右子树查不到任何目标，返回 null；根节点 3 处 left = 5、right = null，返回 left，即 5。LCA = 5，与样例描述 “LCA of nodes 5 and 4 is 5” 一致。

复杂度

• 时间复杂度 O(n)：最坏情况下每个节点都会被访问一次（例如 p、q 都集中在某一侧，另一侧子树也要整体排查）；
• 空间复杂度 O(h)：递归调用栈深度；同样最坏为 O(n)。

两种解法对比

对比维度	68.1 二叉查找树（235）	68.2 普通二叉树（236）
利用的树性质	BST 大小序：左小右大	无，仅利用结构
搜索范围	每层只下降一侧（左或右）	左右子树都要查找
答案判定	第一个使 p、q “左右分裂”的节点（或 p、q 本身）	左右子树结果同时非空的节点；或命中 root == p / root == q 的节点
时间复杂度	O(h)	O(n)
递归栈空间	O(h)	O(h)
能否迭代实现	能，沿路径循环即可（见上文改写）	可用“回溯 + 父节点栈”实现，但代码明显更复杂，递归写法更常用

与仓库中其他树形问题的关联

• 同一组题（235 / 236）也收录在 Leetcode 题解 - 树 的“二叉查找树的最近公共祖先”“二叉树的最近公共祖先”小节中，其解法写法更紧凑（如 235 题把 root == null 判断省略、将两个 if 合并为带 return 的判断），可与本文交叉对照；
• “从某节点出发向上寻找祖先节点”的路径分析与 [8. 二叉树的下一个结点](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/8. 二叉树的下一个结点.md?utm_source=gitcode_repo_files) 高度相似——后者借助父指针向上回溯查找祖先，理解 LCA 时可以把两条思路放在一起比较；
• 两题的递归骨架（基础条件 + 左右子树结果合并）与 [55.1 二叉树的深度](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/55.1 二叉树的深度.md?utm_source=gitcode_repo_files) 等树专题题解一致，是二叉树分治遍历的典型范式，可对照阅读加深理解。