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

LeetCode 236. 二叉树的最近公共祖先递归解法超详细讲解附 C 代码逐行分析大家好今天分享一道二叉树中的经典面试题二叉树的最近公共祖先。这道题在面试和算法题中都非常高频因为它不仅考察你对二叉树遍历的理解还考察你是否真正明白“递归函数返回值到底代表什么”。这篇文章我只讲一种最经典、最推荐的方法递归法。不仅会给出完整代码还会把代码每一行都讲清楚。一、题目描述给定一个二叉树找到该树中两个指定节点p和q的最近公共祖先。最近公共祖先的定义是对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。二、先理解什么叫“最近公共祖先”比如下面这棵树3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4示例 1p 5q 1那么它们的最近公共祖先就是3。因为3是5的祖先3也是1的祖先并且再往下已经没有更深的公共祖先了示例 2p 5q 4那么最近公共祖先就是5。因为题目明确说了一个节点也可以是它自己的祖先。所以如果p本身就是q的祖先那么答案就是p。三、解题思路递归这道题最经典的解法就是递归。我们从当前节点root出发去判断p和q是不是分别出现在当前节点的左右子树中或者当前节点本身是不是p或q递归的核心逻辑对于当前节点root1. 如果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(rootNULL)returnNULL;if(rootp||rootq)returnroot;TreeNode*leftlowestCommonAncestor(root-left,p,q);TreeNode*rightlowestCommonAncestor(root-right,p,q);if(left!NULLright!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(rootNULL)returnNULL;这句表示如果当前节点为空说明这棵子树不存在自然不可能找到p或q所以直接返回NULL。这也是递归必须具备的边界条件之一否则函数会无限往下调用。6. 第二层递归终止条件找到目标节点if(rootp||rootq)returnroot;这句非常关键。如果当前节点本身就是p或者q那么直接返回当前节点。为什么可以这样做因为如果当前节点已经是p那就说明在这棵子树里已经找到了p如果另一个节点在它的下面那么它就可能成为最近公共祖先而题目也明确说了一个节点可以是它自己的祖先所以一旦发现当前节点就是p或q直接返回它就对了。7. 递归查找左子树TreeNode*leftlowestCommonAncestor(root-left,p,q);这句表示去当前节点的左子树中查找p和q并把返回结果保存到left中。这里的left可能有三种含义NULL左子树中什么都没找到p或q左子树中找到了其中一个目标节点某个祖先节点左子树中已经找到了最近公共祖先8. 递归查找右子树TreeNode*rightlowestCommonAncestor(root-right,p,q);同理这句表示去右子树中查找。变量right的含义和left一样。9. 左右都找到了if(left!NULLright!NULL)returnroot;这句是整道题最核心的一句。如果左子树返回值不为空右子树返回值也不为空说明什么说明p和q分别出现在当前节点的左右子树中或者一边找到了其中一个节点另一边找到了另一个节点那么当前节点root一定就是它们的最近公共祖先。所以直接返回root。10. 只有左边找到了if(left!NULL)returnleft;如果右边没找到左边找到了那么就说明p和q都在左子树中或者左子树里已经找到了最近公共祖先这时直接把左边结果往上返回即可。11. 返回右边结果returnright;如果程序执行到这里说明有两种情况左边为空右边不为空左边为空右边也为空无论哪种情况直接返回right都是正确的如果右边找到了就把结果上传如果右边也是空就返回NULL12. 函数结束}递归函数结束。13. 类结束};整个Solution类结束。七、手动模拟一遍我们以这棵树为例3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4设p 5q 1我们从root 3开始第一步看节点 33不是5也不是1继续递归查左子树和右子树第二步查左子树根节点 5发现root p直接返回节点5所以left 5第三步查右子树根节点 1发现root q直接返回节点1所以right 1第四步回到节点 3此时left ! NULLright ! NULL满足if(left!NULLright!NULL)returnroot;所以返回3。这正是答案。八、再看一个特殊情况设p 5q 4那么答案是5。为什么因为在递归到节点5时if(rootp||rootq)returnroot;会直接返回5。而4在5的子树中所以最终返回的最近公共祖先就是5本身。这也体现了题目中的一句话一个节点也可以是它自己的祖先。九、复杂度分析时间复杂度O(n)因为最坏情况下我们需要遍历整棵树一次每个节点最多访问一次。空间复杂度O(h)这里的h是树的高度。原因是递归调用会使用系统栈栈的深度等于树的高度。如果是平衡二叉树空间复杂度约为O(log n)如果是链式退化二叉树空间复杂度最坏为O(n)十、本题用到的知识总结这道题主要用到了以下几个知识点1. 二叉树基础理解每个节点有左右孩子整棵树由根节点递归定义。2. 递归思想把“大问题”拆成“左子树问题”和“右子树问题”。3. 递归终止条件当前节点为空当前节点就是目标节点4. 后序思维这道题本质上是一种“左右子树处理完再根据左右结果决定当前节点返回什么”的过程带有明显的后序遍历思想。5. 返回值设计理解递归函数返回的不只是“找到没找到”而是“当前子树中的有效答案”。6. 最近公共祖先问题的判定逻辑左右都找到当前节点是 LCA只找到一边返回那一边都没找到返回空十一、总结这道题最核心的地方不是代码有多长而是要真正理解这两点递归函数的返回值代表什么为什么左右都不为空时当前节点就是最近公共祖先整道题可以浓缩成一句话在当前节点处如果左子树找到了一个目标节点右子树也找到了一个目标节点那么当前节点就是最近公共祖先。如果你在面试里能把这个逻辑完整讲出来再配上这段简洁代码基本就是非常标准的高质量回答了。十二、附简洁注释版代码classSolution{public:TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){if(rootNULL)returnNULL;// 当前子树为空if(rootp||rootq)returnroot;// 找到 p 或 qTreeNode*leftlowestCommonAncestor(root-left,p,q);// 查左子树TreeNode*rightlowestCommonAncestor(root-right,p,q);// 查右子树if(left!NULLright!NULL)returnroot;// 分别在左右两边当前节点就是 LCAif(left!NULL)returnleft;// 只在左边找到returnright;// 只在右边找到或都没找到}};