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

LeetCode 236. 二叉树的最近公共祖先：递归解法超详细讲解（附 C++ 代码逐行分析）

大家好，今天分享一道二叉树中的经典面试题：二叉树的最近公共祖先。

这道题在面试和算法题中都非常高频，因为它不仅考察你对二叉树遍历的理解，还考察你是否真正明白“递归函数返回值到底代表什么”。

这篇文章我只讲一种最经典、最推荐的方法：递归法。
不仅会给出完整代码，还会把代码每一行都讲清楚。

一、题目描述

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

最近公共祖先的定义是：

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

二、先理解什么叫“最近公共祖先”

比如下面这棵树：

3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4

示例 1

• p = 5
• q = 1

那么它们的最近公共祖先就是3。

因为：

• 3是5的祖先
• 3也是1的祖先
• 并且再往下已经没有更深的公共祖先了

示例 2

• p = 5
• q = 4

那么最近公共祖先就是5。

因为题目明确说了：
一个节点也可以是它自己的祖先。

所以如果p本身就是q的祖先，那么答案就是p。

三、解题思路：递归

这道题最经典的解法就是递归。

我们从当前节点root出发，去判断：

• p和q是不是分别出现在当前节点的左右子树中
• 或者当前节点本身是不是p或q

递归的核心逻辑

对于当前节点root：

1. 如果root为空

说明这棵子树里什么都没有，直接返回NULL。

2. 如果root就是p或者q

说明已经找到目标节点了，直接返回当前节点。

3. 分别去左子树和右子树递归查找

我们会拿到两个返回值：

• left：表示在左子树中找到了什么
• right：表示在右子树中找到了什么

4. 根据左右子树返回值判断结果

• 如果left和right都不为空
  说明p和q分别在当前节点的左右两边
  那么当前节点root就是最近公共祖先

• 如果只有一边不为空
  说明两个目标节点都在这一边，或者这一边已经找到了公共祖先
  直接把这一边的结果返回上去

• 如果两边都为空
  说明这棵子树里没有p和q，返回NULL

四、为什么这个递归是对的？

这道题的关键，不只是把代码背下来，而是要理解：

递归函数返回的到底是什么。

这里我们规定：

lowestCommonAncestor(root, p, q)的返回值表示：
在以root为根的这棵子树中，找到的p、q或者它们的最近公共祖先。

这样就很好理解了：

• 找不到，返回NULL
• 只找到p，返回p
• 只找到q，返回q
• 两个都找到了，返回最近公共祖先

也就是说，这个递归函数的返回值本身就携带了“答案信息”。

五、C++ 代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classSolution{public:TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){if(root==NULL)returnNULL;if(root==p||root==q)returnroot;TreeNode*left=lowestCommonAncestor(root->left,p,q);TreeNode*right=lowestCommonAncestor(root->right,p,q);if(left!=NULL&&right!=NULL)returnroot;if(left!=NULL)returnleft;returnright;}};

六、代码逐行讲解

下面开始逐行拆解这段代码。

1. 结构体定义

structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(NULL),right(NULL){}};

这是题目已经帮我们定义好的二叉树节点。

它表示每个节点里有三部分：

• val：当前节点的值
• left：指向左孩子
• right：指向右孩子

构造函数：

TreeNode(intx):val(x),left(NULL),right(NULL){}

表示创建一个值为x的节点，并把左右孩子初始化为空。

2. 定义类

classSolution{

LeetCode 通常要求把解题函数写在Solution类中。

3.public:

public:

表示下面的方法可以被外部调用。

4. 函数定义

TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){

这是题目要求实现的函数。

它的含义是：

• 输入：
  • root：当前子树的根节点
  • p：第一个目标节点
  • q：第二个目标节点
• 输出：
  • p和q的最近公共祖先节点

返回值类型是：

TreeNode*

也就是说，返回的是一个节点指针。

5. 第一层递归终止条件：空节点

if(root==NULL)returnNULL;

这句表示：

如果当前节点为空，说明这棵子树不存在，自然不可能找到p或q，所以直接返回NULL。

这也是递归必须具备的边界条件之一，否则函数会无限往下调用。

6. 第二层递归终止条件：找到目标节点

if(root==p||root==q)returnroot;

这句非常关键。

如果当前节点本身就是p或者q，那么直接返回当前节点。

为什么可以这样做？

因为：

• 如果当前节点已经是p，那就说明在这棵子树里已经找到了p
• 如果另一个节点在它的下面，那么它就可能成为最近公共祖先
• 而题目也明确说了：一个节点可以是它自己的祖先

所以一旦发现当前节点就是p或q，直接返回它就对了。

7. 递归查找左子树

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

这句表示：

去当前节点的左子树中查找p和q，并把返回结果保存到left中。

这里的left可能有三种含义：

• NULL：左子树中什么都没找到
• p或q：左子树中找到了其中一个目标节点
• 某个祖先节点：左子树中已经找到了最近公共祖先

8. 递归查找右子树

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

同理，这句表示去右子树中查找。

变量right的含义和left一样。

9. 左右都找到了

if(left!=NULL&&right!=NULL)returnroot;

这句是整道题最核心的一句。

如果：

• 左子树返回值不为空
• 右子树返回值也不为空

说明什么？

说明：

• p和q分别出现在当前节点的左右子树中
• 或者一边找到了其中一个节点，另一边找到了另一个节点

那么当前节点root一定就是它们的最近公共祖先。

所以直接返回root。

10. 只有左边找到了

if(left!=NULL)returnleft;

如果右边没找到，左边找到了，那么就说明：

• p和q都在左子树中
• 或者左子树里已经找到了最近公共祖先

这时直接把左边结果往上返回即可。

11. 返回右边结果

returnright;

如果程序执行到这里，说明有两种情况：

• 左边为空，右边不为空
• 左边为空，右边也为空

无论哪种情况，直接返回right都是正确的：

• 如果右边找到了，就把结果上传
• 如果右边也是空，就返回NULL

12. 函数结束

}

递归函数结束。

13. 类结束

};

整个Solution类结束。

七、手动模拟一遍

我们以这棵树为例：

3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4

设：

• p = 5
• q = 1

我们从root = 3开始：

第一步：看节点 3

• 3不是5，也不是1
• 继续递归查左子树和右子树

第二步：查左子树根节点 5

• 发现root == p
• 直接返回节点5

所以：

left = 5

第三步：查右子树根节点 1

• 发现root == q
• 直接返回节点1

所以：

right = 1

第四步：回到节点 3

此时：

• left != NULL
• right != NULL

满足：

if(left!=NULL&&right!=NULL)returnroot;

所以返回3。

这正是答案。

八、再看一个特殊情况

设：

• p = 5
• q = 4

那么答案是5。

为什么？

因为在递归到节点5时：

if(root==p||root==q)returnroot;

会直接返回5。

而4在5的子树中，所以最终返回的最近公共祖先就是5本身。

这也体现了题目中的一句话：

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

九、复杂度分析

时间复杂度

O(n)

因为最坏情况下，我们需要遍历整棵树一次，每个节点最多访问一次。

空间复杂度

O(h)

这里的h是树的高度。

原因是递归调用会使用系统栈，栈的深度等于树的高度。

• 如果是平衡二叉树，空间复杂度约为O(log n)
• 如果是链式退化二叉树，空间复杂度最坏为O(n)

十、本题用到的知识总结

这道题主要用到了以下几个知识点：

1. 二叉树基础

理解每个节点有左右孩子，整棵树由根节点递归定义。

2. 递归思想

把“大问题”拆成“左子树问题”和“右子树问题”。

3. 递归终止条件

• 当前节点为空
• 当前节点就是目标节点

4. 后序思维

这道题本质上是一种“左右子树处理完，再根据左右结果决定当前节点返回什么”的过程，带有明显的后序遍历思想。

5. 返回值设计

理解递归函数返回的不只是“找到没找到”，而是“当前子树中的有效答案”。

6. 最近公共祖先问题的判定逻辑

• 左右都找到：当前节点是 LCA
• 只找到一边：返回那一边
• 都没找到：返回空

十一、总结

这道题最核心的地方，不是代码有多长，而是要真正理解这两点：

1. 递归函数的返回值代表什么
2. 为什么左右都不为空时，当前节点就是最近公共祖先

整道题可以浓缩成一句话：

在当前节点处，如果左子树找到了一个目标节点，右子树也找到了一个目标节点，那么当前节点就是最近公共祖先。

如果你在面试里能把这个逻辑完整讲出来，再配上这段简洁代码，基本就是非常标准的高质量回答了。

十二、附：简洁注释版代码

classSolution{public:TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){if(root==NULL)returnNULL;// 当前子树为空if(root==p||root==q)returnroot;// 找到 p 或 qTreeNode*left=lowestCommonAncestor(root->left,p,q);// 查左子树TreeNode*right=lowestCommonAncestor(root->right,p,q);// 查右子树if(left!=NULL&&right!=NULL)returnroot;// 分别在左右两边，当前节点就是 LCAif(left!=NULL)returnleft;// 只在左边找到returnright;// 只在右边找到，或都没找到}};