1. 题目本质与考点拆解1.1 一句话讲清题目在问什么Leetcode 236 这道题全称是 Lowest Common Ancestor of a Binary Tree刷题圈里一般直接叫它“二叉树最近公共祖先”。题面非常简单给定一棵二叉树以及树上的两个节点 p 和 q要求找出这两个节点最近的公共祖先。这里有几个点必须先掰扯清楚不然后面写代码必踩坑。第一“公共祖先”指的是同时是 p 的祖先和 q 的祖先的节点。第二“最近”指的是这些公共祖先里离根节点最远、离 p 和 q 最近的那个。第三也是很多人第一次做容易忽略的规则一个节点可以成为它自己的祖先。也就是说如果 p 正好是 q 的祖先节点那么 p 本身就是 p 和 q 的最近公共祖先这属于题目的合法答案。题目给的是普通二叉树不是二叉搜索树节点上没有存储父指针所以不能利用排序特性和回溯父节点来走捷径。树的结构可能是极端不平衡的比如一条链走到黑也可能是完全二叉树、满二叉树或者各种奇形怪状的形态。输入限制里明确说明 p 和 q 一定存在于树中且各不相同这两个条件非常重要很多优化和返回逻辑都建立在它们之上。这道题在 LeetCode 上的编号是 236属于中等偏难的经典题在“热门 100 题”里长期稳定占位也是各大厂面试手写算法的热门考题。大部分刷题人第一次见到它都能凭直觉想到“从根往下找分别找 p 和 q 的路径然后比较路径最后一个相同节点”这条路但能一口气写出干净、简洁的递归解法的人其实不多。区别不在于懂不懂递归而在于对递归函数的定义和返回值处理是否想清楚了。1.2 为什么这道题能进“热门 100 题”很多人刷题喜欢按题号顺序刷刷到 236 这道题时可能已经刷了 200 多道但很多人依然会卡一下。这题能进热门百题原因不是它难到天上去而是它非常精准地考查了一个程序员对递归和树形问题的掌握程度。树的问题本质上就是递归的问题。二叉树的天然递归结构决定了大部分树相关的算法题最优解都是用递归去做的。而公共祖先这个问题又恰好是递归思想里一个很有代表性的分支不是在递归过程中收集路径而是在递归回溯的过程中去判断和聚合左右子树返回的结果。这种“自底向上传递信息”的思维模式和“自顶向下传递参数”的思维模式是两个方向。很多人在做树的题目时习惯了往子节点传参数、改状态却不习惯从子节点收结果、做判断。我在实际面试中见过不少候选人一看到这道题就脱口而出“用 DFS 找路径”然后开始写一个 findPath 函数再用两个列表存路径最后比对。这个做法当然能 AC时间复杂度 O(N)空间复杂度 O(N)也能讲得通。但面试官往往会在你写完路径法之后追问一句“能不能不用额外空间能不能一次遍历就拿到结果”如果你没有提前想过递归聚合的解法现场很容易卡住。这题刚好也是后续很多进阶问题的基石。理解了这道题的递归写法再去刷 235二叉搜索树的最近公共祖先、1644带父指针的 LCA、1676多节点的 LCA其实都是同一套思维在不同约束条件下的变体。所以把这题吃透收益是连锁的。1.3 拿到题目后的第一反应我第一次刷这道题的时候第一反应也是路径法从根节点开始 DFS分别找到到 p 和 q 的路径然后从头往后找最后一个相同的节点。这个思路很好理解也很好写但写完之后我总觉得哪里不对劲。路径法需要两个 ArrayList 存路径最坏情况下每条路径长度是 O(N)空间复杂度 O(N)。如果在本地跑测试没什么问题但在面试白板上写代码量偏大而且很容易在“回溯路径”的细节上出错。后来我看了高票答案看到那个只有几行的递归解法时说实话第一反应是“这也太短了是不是有问题”。但仔细推演了一下发现这个解法非常优雅它把问题变成了一个信息聚合问题对于任意一个节点 root我只需要知道它的左子树里有没有 p 或 q右子树里有没有 p 或 q然后根据这两个信息就能判断当前节点是不是答案。这就是典型的“自底向上”思维。递归函数本身不直接去找路径而是分别问左子树和右子树“p 和 q 在不在你这边如果在你这边它们最近的公共祖先是谁”子树回答完之后父节点根据两个子节点的回答做出最终决定。这个思维转换是解这道题最重要的一个坎。跨过去之后你会发现很多树形问题都有了新的解法思路。2. 递归解法的设计思路2.1 递归函数要返回什么先想清楚这个问题递归函数 dfs(root, p, q) 的返回值到底应该是什么很多人写递归习惯先套模板却不先想清楚返回值语义导致写着写着就乱了。这道题的递归函数返回值可以这样定义在以 root 为根的子树中如果 p 和 q 已经全找到了那返回值就是它们的最近公共祖先如果只找到了 p 或 q 中的某一个就返回找到的那个节点如果一个都没找到就返回 null。这个定义听起来有点绕但它非常有用。它允许我们在遍历过程中不依赖外部变量直接把答案通过返回值层层上传。这个设计同时保证了第一一旦在某个节点发现左右两边各有一个目标节点这个节点就是答案可以直接返回第二如果 p 是 q 的祖先那么当递归走到 p 这个节点时p 本身会被作为“找到的唯一一个目标”返回上去。注意返回值的语义和我们平常写的“返回子树中某个节点的值”是不同的。这里的返回值承担了两个角色既是“有没有找到”的标志也是“找到的那个节点本身”。所以一旦 p 或 q 被找到这个节点会一路向上被传递不会被其他非目标节点覆盖。2.2 边界条件怎么定递归解法的边界条件有两个都很直观。第一个边界root null。走到空节点说明没有找到任何东西直接返回 null。第二个边界root p 或 root q。如果当前节点正好是 p 或者 q说明在这棵子树里找到了目标节点之一直接返回 root。这里有个很关键的点如果 p 是 q 的祖先那么当递归到 p 时因为 p 本身匹配直接返回 p这个 p 会一路向上被上层接收最终作为答案输出。这个逻辑天然处理了“节点可以作为自身祖先”的规则。边界条件确定之后递归体其实就是三行代码分别去左子树找去右子树找然后看两个结果。这里有一个细节值得注意因为题目保证 p 和 q 一定存在于树中所以不用额外考虑“没找到答案”的情况。如果题目不保证存在性最终返回值还要做一层判断逻辑会略微复杂。这也是很多面试官会追问的变体后面我会单独展开。2.3 左右子树的四种情况假设当前节点是 root已经分别递归了左子树和右子树拿到了 left 和 right 两个返回值。接下来怎么处理其实只有四种情况left 和 right 都不为 null。这说明 p 和 q 分别位于 root 的左右两侧那么 root 就是它们唯一的公共祖先也是最近的直接返回 root。left 为 nullright 不为 null。说明左子树里什么都没找到而右子树里找到了 p、q 中的一个或者两个。这时候右子树返回的那个节点就是要找的答案直接返回 right。left 不为 nullright 为 null。与上一种情况对称直接返回 left。left 和 right 都为 null。说明 root 的子树里啥也没有返回 null。这四种情况表面上看非常简单但里面最难理解的是第二种和第三种为什么一侧为 null、另一侧非 null 时直接返回非 null 的那一侧这里要回到递归返回值的定义。如果 right 非 null说明右子树里要么找到了一个目标节点要么已经找到了答案。不管是哪一种根据定义这个返回值就是“右子树中的答案或者找到的目标节点”。因为左子树里什么都没找到说明 p 和 q 都不在左子树方向那么所有有效信息都在右子树这边所以右子树的返回结果就是整个 root 子树的返回结果。这个逻辑非常像数学里的单位元思想null 就是这里的单位元任何结果和 null 合并结果不变。所以递归过程本质上是在整棵树上做了一次信息聚合聚合的规则就是“如果两边都有货则当前节点是答案如果只有一边有货则货来自哪边就返回哪边”。2.4 为什么递归在这里是高效方案这个递归解法的时间复杂度是 O(N)其中 N 是二叉树的节点数。因为每个节点最多被访问一次。空间复杂度是 O(H)H 是树的高度。在最坏情况下树退化成链表H 等于 N递归栈会压到 O(N)在平衡二叉树中H 等于 logN空间开销就小得多。相比之下路径法的时间复杂度也是 O(N)但空间复杂度通常是 O(N)因为要存两条路径。而且路径法需要两次 DFS虽然常数时间差异不大但在代码简洁度和面试表达上明显不如递归法。递归法还有一个隐含优势它是单次遍历、边遍历边判断。一旦在某层发现 left 和 right 都非空会直接结束这一层及以上的递归返回不会继续探索其他无关节点。所以实际运行时往往不需要遍历完整棵树就能提前拿到结果。这个特性在树很大的时候体验特别明显。不过追求极致效率的话还可以做一个小小的剪枝如果 left 和 right 都非空直接返回 root无须继续递归。这个剪枝在代码上天然就包含了因为返回值一旦确定就不会再改变。所以这个解法在工程上也可以说是一次遍历、提前终止。3. 完整实现与细节打磨3.1 Java 参考实现先给出最经典的 Java 递归写法这是大多数题解和高票答案采用的形式。class Solution { 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); if (left ! null right ! null) { return root; } return left ! null ? left : right; } }这段代码看起来只有不到十行但信息量非常大。我把每个关键点拆开讲一遍。首先是边界条件的合并写法root null || root p || root q。三个条件写在一起是因为三个条件最终返回的都是 root可以合并分支。如果你刚刚接触递归可能会担心如果 root p但是 p 并不是 q 的祖先直接返回 root 会不会漏掉答案答案是这个返回结果只会被上一层当作“当前子树找到了一个目标节点”来处理不会因为它不是最终答案就报错。最终答案一定是在某个左右子树都非空的节点上被确定下来的。这就是返回值语义设计的精妙之处。然后是递归调用分别去左右子树问结果。这里有个容易迷惑的点为什么 left 和 right 可以直接比较非空因为返回值的定义是“p 或 q 或答案”所以只要非空就说明当前子树里有有效信息。如果 left 和 right 同时非空说明左子树至少含有一个目标右子树也至少含有一个目标鉴于 p 和 q 是两个不同的节点唯一的可能是左右各一个那当前 root 就是答案。如果只有一边非空就把非空的那一边继续向上抛。这里要注意抛回去的不一定是最终答案可能是某个目标节点。但没关系这个目标节点会在更高的层结合另一侧的返回值要么被作为答案返回要么继续被向上抛。这就是信息逐层聚合的过程。3.2 Python 参考实现Python 版本的写法几乎和 Java 一致类定义和 LeetCode 平台的样式保持一致。class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: if root is None or root is p or root is q: return root left self.lowestCommonAncestor(root.left, p, q) right self.lowestCommonAncestor(root.right, p, q) if left is not None and right is not None: return root return left if left is not None else rightPython 版的注意点和 Java 类似但有两个细节要提醒。第一判断用的是is而不是。is比较的是对象引用而 LeetCode 的树节点是对象p、q 是从树里取出来的节点对象所以用is是准确且高效的。会调用对象的__eq__方法如果 TreeNode 没有重写默认退化为对象引用比较但多一次方法调用不划算。刷题时可以养成习惯处理对象节点引用一律用is。第二root is p or root is q这个写法在 Python 中需要注意运算符优先级。is的优先级低于or吗实际上在 Python 中is的优先级高于or所以这个表达式等价于(root is p) or (root is q)没有问题。但如果你写的是root is p or root is q静态检查工具可能会提示加括号更清晰。我自己的习惯是显式加括号避免读者混淆。3.3 复杂度分析时间与空间的真实开销这道题的时间和空间复杂度是面试必问的点不能只会说 O(N)要能讲清楚为什么。时间复杂度 O(N)每个节点被访问一次这个没什么好争议的。但我想补充一句这是最坏情况下的复杂度。如果 p 和 q 在树中靠得比较近比如就在某棵小子树里递归在找到了 LCA 之后上层会因为 left 和 right 两个结果中已经包含了答案而直接返回不再访问其他分支。所以实际平均执行时间通常小于 N。空间复杂度 O(H)递归过程中系统栈的深度等于树的深度。树是斜树的情况下H N空间复杂度退化为 O(N)。树是平衡二叉树的情况下H logN空间复杂度是 O(logN)。这个 H 通常被忽略但在面试里面试官喜欢追问这个点你需要把“递归栈即树高”这个关联讲清楚。还有一个常见的追问如果要用迭代法实现空间复杂度能做到 O(1) 吗答案是不能。只要给定的是普通二叉树且没有父指针最坏情况下必须记录访问路径空间下界就是 O(H)。如果题目条件是二叉搜索树可以利用特性实现 O(H) 时间、O(1) 空间那是另一道题Leetcode 235。3.4 细节节点自身的祖先身份前面反复提到“节点可以是它自己的祖先”这个规则在题目描述里有明确说明但不少人第一次做题时会下意识地忽略导致在 p 是 q 的祖先、或者 q 是 p 的祖先的情况下写出错误的代码。举个例子假设 p 是根节点q 在右子树中。按照常规的路径法找公共祖先路径包含 p 和 q那么公共节点是 p 吗是的因为 p 是 q 的祖先。但在递归法中这个过程更隐蔽递归从根节点开始第一层就会触发root p的边界条件直接返回 p。这时候右子树的递归其实还没有执行p 就作为返回值一路向上传。最终整棵树的返回值就是 p正确。但如果你的边界条件漏写了root p || root q那递归就会继续往下深入直到在某层发现 left 或 right 非空。这个做法不是不能做而是逻辑会变得更复杂你需要在回溯过程中判断“当前节点是否等于 p 或 q”如果不是再去聚合左右子树的结果。代码会变长而且容易在“根节点就是答案”的情况下漏掉答案。所以边界条件里的root p || root q不是可选项而是必选项。它是整个递归逻辑正确性的基石去掉它之后递归仍然可能偶尔跑对但遇到 p 是 q 祖先的情况就会出错。4. 同类变体与面试延伸4.1 BST 情形的快速解法Leetcode 235如果题目限定是二叉搜索树那解法就完全不一样了。利用二叉搜索树左小右大的特性从根节点开始向下走如果 p 和 q 都小于当前节点说明 LCA 在左子树往左走。如果 p 和 q 都大于当前节点说明 LCA 在右子树往右走。如果 p 和 q 一个在左一个在右或者当前节点正好等于 p 或 q那么当前节点就是 LCA。这个解法的时间复杂度是 O(H)空间复杂度 O(1)迭代版本比普通二叉树的 O(N) 要快得多。它是 236 题的“福利版”很多面试官会先让你做 236再追问一句“如果这棵树是 BST 呢”看你能不能利用题目给你的额外条件优化复杂度。我建议在刷题时把这两题放在一起对比学习。你会发现同一个“最近公共祖先”问题在普通二叉树和二叉搜索树下的解法一个靠递归聚合一个靠方向判断思维路径完全不同。这也提醒你面对题目先确认输入有没有可以利用的特殊结构比一上来就套递归模板要重要得多。4.2 带父指针的 LCA另一个常见变体是树的节点除了 left 和 right 之外还有一个 parent 指针。这种结构下问题就变成了“两个链表找交点”问题。思路非常简单从 p 出发沿着 parent 指针一直向上走到根把经过的所有节点存到一个 Set 里。然后从 q 出发沿着 parent 指针向上走遇到的第一个在 Set 中的节点就是 LCA。时间复杂度 O(H1 H2)H1 和 H2 分别是 p 和 q 到根的距离空间复杂度 O(H1)用于存储 Set。还可以进一步优化空间让 p 和 q 先分别向上走到根记录深度或路径长度然后深度较深的节点先向上走直到两个节点深度相同再同步向上走相遇节点就是 LCA。这种做法类似于链表相交问题中提到的快慢对齐法空间复杂度可以降到 O(1)。这个变体的价值在于它把你的思维从“树”拉到了“链”上。很多看起来没有关联的题目在抽象层面其实是一样的。4.3 多个节点的 LCA如果是三个或更多节点的 LCA递归解法也能扩展。一种做法是把多节点问题转换成两两合并。比如三个节点 a、b、c先求 LCA(a, b) x再求 LCA(x, c) 最终答案。这个思路正确因为 LCA 满足结合律。不过这样会做多次遍历效率不是最高的。更高效的做法是扩展递归参数递归函数接收一个节点集合 targetSet返回值语义是“在这棵子树中如果目标集合中的所有节点都已经找到了返回最近公共祖先如果只找到了部分节点返回这些节点中深度最深的那个如果一个都没找到返回 null”。这样一次遍历就能完成全部查找。这个变体很少出现在面试中但在实际工程问题里很有价值比如一个分布式系统中的多个节点需要求公共祖先或者在一棵组织结构树里找到多个员工的共同汇报上级。4.4 迭代实现与路径法如果你更习惯迭代思路也可以用栈模拟 DFS先找到 p 和 q 各自到根节点的路径再比对路径。这个做法的优势和劣势都非常明显。优势是直观没有递归那么绕适合在白板上和面试官一步步对齐思路。做法是用栈做后序遍历同时用 MapTreeNode, TreeNode 记录每个节点的父节点。遍历完所有节点后就能从 p 和 q 一路顺着父节点回溯到根拿到两条路径。把 p 的路径存到 Set然后让 q 从自身开始向上走第一个出现在 Set 中的节点就是答案。劣势是代码量大且需要额外的 Map 存储父节点关系。面试如果追求简洁递归法明显更优。但如果你想展示“我有多种解法且理解它们各自的时空开销”路径法可以作为备选方案讲一讲。// 迭代法参考思路Java public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { MapTreeNode, TreeNode parent new HashMap(); DequeTreeNode stack new ArrayDeque(); parent.put(root, null); stack.push(root); while (!parent.containsKey(p) || !parent.containsKey(q)) { TreeNode node stack.pop(); if (node.left ! null) { parent.put(node.left, node); stack.push(node.left); } if (node.right ! null) { parent.put(node.right, node); stack.push(node.right); } } SetTreeNode ancestors new HashSet(); while (p ! null) { ancestors.add(p); p parent.get(p); } while (!ancestors.contains(q)) { q parent.get(q); } return q; }5. 常见错误与现场调试记录5.1 常见错误速查表我把这几年在面试和刷题中见过的常见错误整理成一张速查表方便大家自查。错误类型具体表现影响位置解决办法误用二叉搜索树特性用p.val root.val判断方向但题目给的是普通二叉树所有输入先看清题目是普通二叉树还是 BST边界漏写漏掉 root proot q误用为isPython节点比较用在自定义类上可能出问题引用比较统一用is返回值语义混乱递归函数一会儿返回 Boolean 一会儿返回节点逻辑全盘出错先明确函数签名再写代码忽略 null 检查直接调用left.val但 left 可能为 null空指针异常先判断 left 是否为空在递归函数里改全局变量用全局变量存答案但没设置终止条件答案被后续覆盖优先用返回值不用全局变量认为必须找到路径死磕路径提取不知道可以直接聚合返回思路卡住理解自底向上聚合思想这里我想重点说一个同学们最容易犯的错误在一个递归函数里既想返回“是否找到了”又想返回“找到的节点”结果用全局变量或者一个长度为 1 的数组去绕把代码写得很丑。其实一个返回值完全可以同时承载这两个信息返回 null 就是没找到返回非 null 就是找到的节点根本不需要额外的标志位。还有一个比较隐蔽的错误递归调用时左右子树的调用参数顺序写反。lowestCommonAncestor(root.left, p, q)和lowestCommonAncestor(root.right, q, p)从数学上是一样的因为 LCA 的结果和参数顺序无关但如果你在递归中混用了 p 和 q 的位置代码可读性会下降也容易让面试官怀疑你对函数的理解。5.2 面试时的答题节奏这道题在面试中出现频率极高我建议按下面的节奏来答稳扎稳打。拿到题先确认约束条件。向面试官确认这棵树是否为二叉搜索树节点上是否有 parent 指针p 和 q 是否一定存在于树中这几个问题的答案直接影响解法选择。实际上 LeetCode 原题已经给出了大部分约束但面试现场多问一句不是坏事反而显得你思考缜密。然后从最直观的路径法讲起快速向面试官展示你能理解问题的基本解法。讲完之后主动说“这个方法是 O(N) 时间和 O(N) 空间但树的问题通常可以用递归做优化我再试一下递归解法”。这时再写递归版本面试官会觉得你是有层次地在优化而不是一上来就背答案。写递归版本的代码时一边写一边讲解四个核心点边界条件、左右子树递归、双非空返回当前节点、单侧非空返回该侧。这四句话正好对应代码的四段结构能帮助面试官跟上你的思路。写完代码后主动跑一个简单的例子验证。用一个三层的树p 和 q 分别位于左子树和右子树手动推演一遍递归过程确认返回的是根节点。再跑一个极端例子p 是根节点q 在深层的右子树中确认边界条件能正确返回 p。最后回答复杂度问题并说明空间复杂度受树高影响。如果面试官要求更严格可以补充“如果树是一条斜链递归深度为 N我们也可以用迭代法避免栈溢出”这句话能体现你对工程问题的敏感度。5.3 我的刷题复盘心得刷完这道题之后我做了一个小复盘想在这里分享给正在刷题的朋友。首先这道题是“热门 100 题”里少有的“几十行递归能解决、但理解成本很高”的题目。如果你第一次没看懂高票答案不要怀疑自己很正常。我当时是看完题解之后自己在白纸上手动模拟了一棵 5 节点的小树把递归调用过程一步步展开写下来才真正弄明白返回值是怎么一路传上去的。这个过程花了大概半小时但效果非常好之后我再也没忘过这个解法。建议你也试试“手推递归”这个方法。选一棵最简单的小树把每个节点的 left、right 返回结果写在纸上然后从叶子节点一步步往上算。你会发现递归的每一次返回其实就是在做一道“两个子树的答案合并”的小题合并规则就是那四种情况。其次这道题非常适合用来练习“先定义返回值再写递归体”的方法论。很多人写递归容易写成“试探性递归”边写边猜返回值是什么结果代码改来改去。如果你能在写函数体之前先用一句话讲清楚“返回值是什么”那这道题的递归就十拿九稳了。这个方法对所有树形递归题目都适用。最后说一句私心话LeetCode 上很多题目刷一遍过几天就忘了这道题属于刷一遍能记住很久的那种。因为它背后的“聚合”思想太通用了从 LCA 到二叉树的序列化、从计算子树大小到判断平衡二叉树全都是这个套路。把这道题吃透等于你同时掌握了十几道中等难度树题的内功心法。5.4 实际调试中遇到的边界案例再来分享几个我在调试时用过的测试用例这些用例能帮你快速验证代码是否正确。第一个用例单节点树。root 既是 p 又是 q。这种情况非常基础但也最容易出错。按照边界条件直接返回 root正确。第二个用例斜树退化成链表p 在最底层q 在中间层。比如 1-2-3-4-5 的一条链p 是 5q 是 3。递归会一路走到最底层然后回溯时依次处理。因为 p 和 q 在同一侧所以每个节点的 left 和 right 只有一个非空返回值会一路向上最终在节点 3 处因为 left 非空来自 4 和 5 的递归结果、right 为 null把 left 抛上去答案就是 3正确。第三个用例p 和 q 分别在深度很深的左右两侧。此时递归会在它们的共同祖先处触发“left 和 right 都非空”的条件直接返回该祖先节点。这个用例可以验证递归的提前终止机制是否正确。第四个用例p 和 q 都在左子树且 p 是 q 的祖先。比如一棵树根节点 1左子节点 22 的左子节点 3p 是 2q 是 3。递归过程如下根节点 1 的左子树递归去查进入节点 2发现 root p直接返回 2。节点 1 的 right 返回 null。最终节点 1 的 left 非空、right 为空返回 left即 2答案正确。这个用例特别能检验“节点自身是祖先”的处理。把这些用例保存在本地或者笔记里刷其他变体题时可以直接复用节省调试时间。6. 从刷题到应用的延伸思考这道题看起来是纯粹的面试算法题但它的思想在实际工程中其实有对应场景。一棵二叉树可以代表很多真实世界的结构组织结构、文件目录、继承体系、路由表、决策树等等。比如在组织架构系统里找两个员工的最近共同汇报上级本质上就是 LCA。在 Git 的提交历史里两个分支的最近公共提交节点也是 LCA 的变体应用。在编译器里抽象语法树AST中两个语法节点的最近公共父节点更是非常常见的操作。掌握了 LCA 的递归思维你在遇到这些业务问题时会有一种“这题我见过”的底气。另外从 LeetCode 的刷题节奏来看236 是一个很典型的分水岭它前面的题大多考查“你会不会某个数据结构”它后面的很多题考查“你能不能在一个复杂问题里抽取出递归关系”。把 236 的递归返回值语义彻底弄明白之后你会发现后续刷二叉树的题目思路通畅了很多。我自己在实际编码中也慢慢形成了一个习惯写任何递归函数之前先问自己“这个函数的返回值在每一层递归中承载的是什么信息”。这个问题一旦想清楚代码的正确性就有了八成把握。剩下的两成靠边界条件和测试用例兜底。这个习惯就是从 236 这道题里养成的所以每次有人让我推荐一道“值得反复琢磨”的题我总会提起它。最后再分享一个小技巧如果你在面试现场实在想不起来递归解法路径法完全可以兜底。先用路径法讲清楚思路让面试官看到你的思维是通的然后主动说“我知道还有一种更精简的递归解法我可以尝试写一下”。这种处理方式比憋了半天一个字都写不出来要好得多。算法水平是日积月累的但应对面试的节奏感是可以提前准备的。
