跳到主要内容

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

必学第 7 章 · 树上综合问题

本节目标

用后序递归让左右子树按节点身份报告目标，在信息首次汇合处找到 LCA。

这是树上综合问题中“左右信息汇合”的母题。通用的子树返回接口可先回顾子树信息与递归判断；本题的报告具体是目标节点或已经确定的祖先。

查看 LeetCode 原题

题意与边界​

给定树中的两个不同节点 p、q，返回深度最大的共同祖先。原题保证两个节点都在树中；祖先包含节点自身，所以一个目标位于另一个目标子树中时，较高的目标就是答案。节点值可以重复，判断“命中目标”必须比较节点身份。

返回值语义​

令 find(root, p, q) 返回：当前子树没有目标时为空；只找到一个目标时返回该目标；两个目标已经在当前子树汇合时返回它们的 LCA。空节点直接返回空，命中 p 或 q 直接返回当前节点。

递归取得 left、right 后，若两侧都非空，两个目标分别从不同分支报告，当前节点就是首次汇合处；若只有一侧非空，原样向上继续报告。后序回程从深到浅，因此首次汇合的一定是最近公共祖先。

正确性依据​

对任意子树归纳。空树不包含目标，基础返回正确。非空子树中，若根命中目标，根可作为自己的祖先；否则递归假设保证两侧返回值正确。两侧均非空时，两个目标分居当前根的两侧，根是最近共同祖先；单侧非空时，所有有效信息都在这一侧，原样返回保持语义。故根调用返回所求 LCA。

代码实现​

C++17
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 基线返回：空节点或命中目标
        if (root == nullptr || root == p || root == q) {
            return root;
        }

        // 递归搜索左右子树
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        // 两侧命中，当前节点为最近公共祖先
        if (left != nullptr && right != nullptr) {
            return root;
        }
        return left != nullptr ? left : right;
    }
};

C++ 用 root == p，Python 用 root is p 比较节点身份；两者都不依赖节点值。行为测试额外放入两个值为 2、两个目标值为 3 的不同节点，确保不会按值误判。

复杂度分析​

每个节点至多访问一次，时间复杂度为 O(n)。递归调用栈深度为树高 h，额外空间为 O(h)。

边界与易错点​

  • 一个目标是另一个的祖先时，命中目标必须立刻返回。
  • 左右均非空才在当前节点汇合；单侧非空要继续上传该节点。
  • 不能把 root.val == p.val 当作命中条件，重复值并不代表同一节点。
  • 简洁模板依赖“两个目标都存在”；允许目标缺失的变体需额外记录找到的目标数。

模式迁移​

当子树报告的不是节点而是高度、合法性或路径贡献时，仍保留“定义返回值—合并左右信息”的顺序。若答案由左右两侧共同组成，但父节点只能继续使用单侧信息，可继续迁移到最大路径和。