算法

二叉树的最近公共祖先

loser

31 Aug 2026 • 11 min read

给定一个二叉树，找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：

对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大。

一个节点也可以是它自己的祖先。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5，因为一个节点可以是它自己的祖先。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 10^5] 内
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同
p != q
p 和 q 均存在于给定的二叉树中

解法一（后序 DFS）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
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;
        }

        if (left != nullptr)
        {
            return left;
        }

        return right;
    }
};

解法二（父指针 + 哈希集合）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        unordered_map<TreeNode*, TreeNode*> parent;
        queue<TreeNode*> que;

        parent[root] = nullptr;
        que.push(root);

        while (parent.find(p) == parent.end() || parent.find(q) == parent.end())
        {
            TreeNode* node = que.front();
            que.pop();

            if (node->left != nullptr)
            {
                parent[node->left] = node;
                que.push(node->left);
            }

            if (node->right != nullptr)
            {
                parent[node->right] = node;
                que.push(node->right);
            }
        }

        unordered_set<TreeNode*> ancestors;

        while (p != nullptr)
        {
            ancestors.insert(p);
            p = parent[p];
        }

        while (ancestors.find(q) == ancestors.end())
        {
            q = parent[q];
        }

        return q;
    }
};

核心思想

这题是普通二叉树，不是二叉搜索树。

所以不能根据节点值大小去决定往左走还是往右走。

最近公共祖先的关键是看 p 和 q 分别落在哪些子树里。

对于当前节点 root：

如果 p 和 q 分别出现在左右子树中，那么 root 就是它们的最近公共祖先。
如果 p 和 q 都在左子树中，那么答案一定在左子树里。
如果 p 和 q 都在右子树中，那么答案一定在右子树里。
如果当前节点本身就是 p 或 q，那么当前节点可能就是最近公共祖先。

这题最关键的观察是：

一个节点能成为最近公共祖先，当且仅当它的左右子树分别找到了 p 和 q，或者它自己就是其中一个节点并且另一个节点在它的子树中。

因此可以用后序 DFS。

先递归处理左右子树，再根据左右子树返回的信息决定当前节点应该返回什么。

解法一：后序 DFS

递归函数：

lowestCommonAncestor(root, p, q)

表示：

在以 root 为根的子树中，寻找 p 和 q 的最近公共祖先；如果只找到其中一个节点，就返回这个节点；如果都没找到，就返回 nullptr。

递归边界有两种：

if (root == nullptr || root == p || root == q)
{
    return root;
}

如果 root == nullptr，说明当前子树为空，返回 nullptr。

如果 root == p 或 root == q，说明当前节点就是目标节点之一，直接返回当前节点。

然后分别在左右子树中查找：

TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);

根据返回结果分情况讨论。

左右子树都找到

如果：

left != nullptr && right != nullptr

说明 p 和 q 分别位于当前节点的左右两侧。

它们第一次汇合的位置就是当前节点 root，所以返回 root。

只有一边找到

如果只有左子树返回非空，说明 p 和 q 都在左子树中，或者左子树中只找到了其中一个节点。

由于题目保证 p 和 q 都存在，如果当前右子树没有返回任何目标节点，那么最近公共祖先一定在左子树返回结果中。

右子树同理。

所以返回非空的一边：

return left != nullptr ? left : right;

两边都没找到

如果左右子树都返回 nullptr，说明当前子树中没有 p 或 q。

此时返回 nullptr。

为什么可以返回目标节点本身

题目说明：

一个节点也可以是它自己的祖先。

例如 p = 5，q = 4，并且 4 在 5 的子树中。

当 DFS 到节点 5 时，直接返回 5。

它的祖先节点再往上处理时，会发现只有一侧返回了 5，另一侧没有新的目标节点。

因此最终答案仍然是 5。

这正好符合最近公共祖先可以是节点本身的定义。

解法二：父指针 + 哈希集合

另一个思路是先记录每个节点的父节点。

从根节点开始做 BFS，用哈希表保存：

unordered_map<TreeNode*, TreeNode*> parent;

其中：

键：当前节点
值：当前节点的父节点

得到父指针后，从 p 一路向上走到根节点，把沿途所有祖先放进集合：

unordered_set<TreeNode*> ancestors;

然后从 q 一路向上走。

第一个出现在 ancestors 中的节点，就是 p 和 q 的最近公共祖先。

原因是 q 是从自己开始向上走的，越早遇到的公共祖先深度越大，也就越“近”。

为什么比较节点指针而不是节点值

代码中判断目标节点时使用：

root == p
root == q

这比较的是节点本身，而不是节点值。

虽然题目保证所有 Node.val 互不相同，用值比较也能定位节点，但函数参数给的是节点指针。

直接比较指针更准确，也更符合题目的接口语义。

边界情况

如果 p 是 q 的祖先，那么最近公共祖先就是 p。

如果 q 是 p 的祖先，那么最近公共祖先就是 q。

如果 p 和 q 分别位于根节点的左右子树，那么最近公共祖先就是根节点。

如果整棵树退化成一条链，两个节点的最近公共祖先就是深度较小的那个节点。

题目保证 p 和 q 都存在于树中，所以不需要处理目标节点缺失的情况。

正确性证明

我们证明：两个解法都能返回 p 和 q 的最近公共祖先。

结论 1：递归返回值能正确表示当前子树中的目标信息

对于空子树，递归返回 nullptr，表示没有找到 p 或 q。

如果当前节点就是 p 或 q，递归返回当前节点，表示当前子树中找到了一个目标节点。

如果当前节点不是目标节点，递归会分别检查左右子树。

因此，递归返回值始终能表示当前子树中是否包含 p 或 q，以及在已经找到最近公共祖先时返回该祖先节点。

结论 2：当左右子树都返回非空时，当前节点就是最近公共祖先

如果左子树和右子树都返回非空，说明 p 和 q 分别位于当前节点的左右两侧。

任何位于左子树内部的节点都不可能是右子树中节点的祖先。

任何位于右子树内部的节点也不可能是左子树中节点的祖先。

所以能同时作为 p 和 q 祖先的最低节点，就是当前节点 root。

因此返回 root 正确。

结论 3：当只有一侧返回非空时，最近公共祖先在这一侧

如果只有左子树返回非空，右子树没有找到任何目标节点。

由于题目保证 p 和 q 都在整棵树中，那么当前子树中已经找到的目标信息只能来自左子树。

如果左子树返回的是某个目标节点，说明当前子树中目前只确定找到了这个目标节点，需要继续把它向上传递，让祖先节点判断另一个目标节点在哪里。

如果左子树返回的是最近公共祖先，那么当前节点不需要改变这个结果。

右子树返回非空的情况同理。

所以只有一侧非空时，返回这一侧的结果是正确的。

结论 4：如果当前节点本身是目标节点，并且另一个目标节点在它的子树中，当前节点会被保留下来

当 root == p 或 root == q 时，算法直接返回 root。

根据定义，一个节点可以是它自己的祖先。

如果另一个目标节点在 root 的子树中，那么 root 同时是两个节点的祖先，并且没有比 root 更深的节点能同时作为二者祖先。

所以当前节点本身就是最近公共祖先。

算法返回 root 正确。

结论 5：算法不会漏掉真正的最近公共祖先

真正的最近公共祖先一定满足以下两种情况之一：

p 和 q 分别在它的左右子树中。
它自己是 p 或 q 中的一个，并且另一个节点在它的子树中。

第一种情况会由结论 2 在该节点处返回。

第二种情况会由结论 4 在该节点处返回。

因此真正的最近公共祖先一定会被算法返回，不会被遗漏。

结论 6：父指针解法找到的第一个公共祖先就是最近公共祖先

父指针解法先记录每个节点的父节点。

然后从 p 开始不断向上走，把 p 以及 p 的所有祖先加入集合。

接着从 q 开始不断向上走。

因为这个过程是从 q 自己开始，按深度从大到小依次访问 q 的祖先，所以第一次遇到已经在集合中的节点时，它就是深度最大的公共祖先。

深度最大的公共祖先正是最近公共祖先。

因此父指针解法也正确。

得出结论

由结论 1 可知，递归返回值能正确表达当前子树是否包含目标节点。

由结论 2 可知，左右子树分别找到目标节点时，当前节点就是答案。

由结论 3 可知，只有一侧找到目标信息时，返回这一侧不会丢失答案。

由结论 4 可知，目标节点本身作为祖先的情况能正确处理。

由结论 5 可知，算法不会漏掉真正的最近公共祖先。

由结论 6 可知，父指针解法找到的公共祖先也是最近公共祖先。

因此两个解法都正确。

举例理解

以：

root = [3,5,1,6,2,0,8,null,null,7,4]
p = 5
q = 1

为例，这棵树可以理解为：

在节点 3 处：

左子树能找到节点 5
右子树能找到节点 1

因此节点 3 是它们第一次汇合的位置，也是最近公共祖先。

再看：

p = 5
q = 4

节点 4 位于节点 5 的子树中。

因为一个节点可以是它自己的祖先，所以 5 同时是 5 和 4 的祖先。

并且不存在比 5 更深的节点还能同时作为二者祖先。

所以最近公共祖先是：

复杂度分析

设二叉树节点数为 n，树的高度为 h。

解法一

每个节点最多被访问一次。

时间复杂度：O(n)
空间复杂度：O(h)

空间复杂度来自递归调用栈。

解法二

建立父指针时，每个节点最多入队、出队一次。

之后从 p 和 q 向上走，最多各走 h 步。

时间复杂度：O(n)
空间复杂度：O(n)

空间复杂度来自父指针哈希表、队列和祖先集合。