想当初刚开始刷二叉树的时候我一度以为只要把前中后序遍历和层序遍历吃透就够了。结果刷到这个系列的第十五篇迎面撞上的几道题——路径总和、从中序与后序构造二叉树、最大二叉树、合并二叉树——直接把我之前那点遍历自信打碎了。这些题表面上看还是二叉树本质上却从按顺序访问节点变成了在递归过程中做决策、记录路径、反推结构。这一篇就把这几道题放在一起复盘路径总和这类问题考的是递归返回值怎么设计构造类问题考的是区间怎么切分不重不漏合并类问题考的是空节点怎么处理。如果你也正好卡在这一批题上建议先别急着往下刷把这几个核心套路理清楚后面的二叉搜索树题目会顺很多。1. 路径总和到底在考什么递归返回值设计的三种形态1.1 为什么路径总和比所有路径简单先看要不要返回值路径总和这道题的描述很直接给一棵二叉树和一个目标值判断是否存在一条从根节点到叶子节点的路径路径上所有节点值加起来刚好等于目标值。这个判断是否存在的需求决定了递归函数可以设计成返回布尔值。因为只要找到一条合法路径整道题就可以结束了不需要继续跑完剩下所有分支。def hasPathSum(root: TreeNode, targetSum: int) - bool: if root is None: return False if root.left is None and root.right is None: return root.val targetSum return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)这里有一个很关键的设计我没有维护一个累加变量而是把目标值不断减去当前节点值。每往下走一层剩余要凑的数就减少当前节点的值走到叶子节点时只需要判断叶子节点的值是不是等于剩余的目标值。这个转换在路径类题目里非常常见。与其带一个 sum 变量到处传不如直接把目标值当参数递归传递省掉一层状态维护代码也简洁不少。另外要注意终止条件的选择。我判断的是叶子节点而不是空节点因为题目要求路径必须从根到叶子。如果写成空节点返回 False功能上也能跑但会多走一层无效递归并且遇到空树的情况还需要额外处理。判断叶子节点更贴合题意效率也更好。1.2 路径总和II从找到一条变成找齐所有返回值就不够了路径总和II升级了不仅要判断存在还要把所有满足条件的路径全部找出来。这时候问题性质变了递归函数的返回值设计也得跟着变。如果你还沿用第一题的写法让递归函数返回布尔值麻烦就来了。一旦在某个分支找到了合法路径函数就 return 了剩下那些同样可能满足条件的分支根本来不及访问。所以这题的正确写法是递归函数不返回值而是通过参数传递两个东西——一个收集结果的数组一个记录当前路径的数组。def pathSum(root: TreeNode, targetSum: int) - List[List[int]]: res [] def dfs(node: TreeNode, remain: int, path: List[int]): if not node: return if not node.left and not node.right and remain node.val: res.append(path [node.val]) return dfs(node.left, remain - node.val, path [node.val]) dfs(node.right, remain - node.val, path [node.val]) dfs(root, targetSum, []) return res这里我用的是path [node.val]也就是每次递归生成一条新路径上层函数拿到的 path 完全不受影响。这样写最省心不需要手动恢复现场。但很多人会问那是不是不用学回溯了不是的。另一种更经典的写法是显式回溯用path.append(node.val)和path.pop()配合。两种写法都能过但显式回溯对理解恢复现场这个概念更有帮助尤其是后面刷那些更复杂的回溯题时脑子里如果有了递归回来要撤销刚才的选择这个意识会好写很多。还有一个小坑必须提醒如果你选择显式回溯在把 path 加入结果的时候一定要写res.append(path[:])或者res.append(list(path))不能直接res.append(path)。因为 path 是引用传递后面递归返回时还会被继续修改直接 append 的话最后 res 里存的其实是同一个列表的引用回溯完就全变成空列表了。这个错误很隐蔽调试的时候中间态看着都对最后结果却离奇消失。1.3 三种返回值形态对照路径类题目的选择标准把路径类题目做多了你会发现递归函数的返回值其实就三种形态选择标准很清晰返回布尔值只需要判断存在性找到一条合法路径就提前终止。路径总和第一题就是这种。不返回值需要遍历整棵树把所有满足条件的结果收集起来。路径总和II、二叉树的所有路径都是这种。返回计算值子树要把某种信息汇总给父节点比如最大深度、节点数量、平衡判断等。我在这一篇里反复强调返回值设计是因为这直接决定代码能不能正确表达搜索意图。返回值选错了代码怎么改都是别扭的。判断是否提前终止、是否收集全部结果这两个问题一确定返回值设计基本就出来了。这个选择标准不只是路径类题目适用整个二叉树递归题都是同一个逻辑。先想清楚这一层递归要往上返回什么再动手写比盲目套模板要可靠得多。2. 从中序后序构造二叉树先搞清楚两个序列是怎么切出来的2.1 后序的最后一个元素是根中序把序列切成两半从中序遍历和后序遍历构造二叉树是构造类题目里最经典的一道。很多人拿到题目第一反应是懵两个数组怎么还原一棵树别急着背代码先理解切分原理。中序遍历的顺序是左-根-右所以只要在中序序列里找到根节点的位置根左边那一截就是整棵左子树的中序右边那一截就是整棵右子树的中序。后序遍历的顺序是左-右-根所以后序序列的最后一个元素一定是根节点。问题来了后序序列剩下那一大段里左子树和右子树的分界线在哪答案是要借助中序切出来的左子树长度来判断。左子树有多少个节点后序序列前面就有多少个节点属于左子树。拿一个具体例子走一遍就清楚多了。假设中序是[9, 3, 15, 20, 7]后序是[9, 15, 7, 20, 3]后序最后一个元素是 3所以根节点值是 3。在中序里找到 3下标是 1所以左子树中序是[9]右子树中序是[15, 20, 7]。左子树长度是 1所以后序里前 1 个元素[9]是左子树后序剩下的[15, 7, 20]是右子树后序。注意这里有一个很多人转不过弯的点为什么后序的右子树段是[15, 7, 20]看起来和中序右子树[15, 20, 7]顺序不一样因为后序是左-右-根的顺序右子树的根 20 不一定在最后。但左右子树分界线完全由左子树长度决定这个长度从中序里能精确拿到所以不会切错。2.2 切片写法最容易理解但面试建议写下标区间理解了切分逻辑之后第一版代码用切片写是最直观的def buildTree(inorder: List[int], postorder: List[int]) - TreeNode: if not postorder: return None root_val postorder[-1] root TreeNode(root_val) if len(postorder) 1: return root index inorder.index(root_val) left_inorder inorder[:index] right_inorder inorder[index 1:] left_postorder postorder[:len(left_inorder)] right_postorder postorder[len(left_inorder):-1] root.left buildTree(left_inorder, left_postorder) root.right buildTree(right_inorder, right_postorder) return root切片写法最大的好处是思路直接每一层递归处理的是新的小数组边界问题少。但缺点也明显每次递归都要复制数组空间开销大而且每次都要用inorder.index(root_val)线性查找根节点位置时间开销也不小。面试的时候这份代码大概率能过但如果你想让代码更上一层楼建议改成下标区间 哈希表的写法。def buildTree(inorder: List[int], postorder: List[int]) - TreeNode: index_map {value: idx for idx, value in enumerate(inorder)} def dfs(in_left, in_right, post_left, post_right): if post_left post_right: return None root_val postorder[post_right - 1] root TreeNode(root_val) root_idx index_map[root_val] left_len root_idx - in_left root.left dfs(in_left, root_idx, post_left, post_left left_len) root.right dfs(root_idx 1, in_right, post_left left_len, post_right - 1) return root return dfs(0, len(inorder), 0, len(postorder))这份代码里所有区间统一采用左闭右开。这是我自己写构造类题目最在意的一个约定开闭必须统一。今天写左闭右开明天写左闭右闭一旦忘了调整终止条件和边界代码非常难调。拆解一下边界后序的根在post_right - 1因为右端点不包含。左子树的后序区间从post_left开始连续left_len个右子树的后序区间从post_left left_len开始到post_right - 1结束。中序的左子树区间是[in_left, root_idx)右子树区间是[root_idx 1, in_right)。只要把这里想明白前序中序构造其实就是把根的位置从末尾挪到开头其余完全一样。2.3 前序后序为什么不能唯一确定二叉树顺着这个题往下想有人会问那用前序和后序能构造二叉树吗答案是不一定能唯一确定。前序确定根在最前面后序确定根在最后面但左右子树的分界线无法确定。举个最简单的例子一棵只有两个节点的树根是 1孩子是 2。前序是[1, 2]后序是[2, 1]但 2 可以是 1 的左孩子也可以是 1 的右孩子前序和后序根本无法区分这两种情况。所以当你在刷题群里看到只用前序后序重建二叉树的题目要么题目额外给了条件比如二叉搜索树或者满二叉树要么题目问的就是为什么无法唯一确定。这个知识盲区提前补上面试被问到不至于懵。3. 最大二叉树的构造思路递归函数的入参该设计成什么3.1 最大二叉树递归构造的第二个典型模板最大二叉树这道题的规则是给定一个不含重复元素的整数数组数组中的最大值作为根节点最大值左边的子数组递归构造左子树右边的子数组递归构造右子树。乍一看跟题目本身没关系但做进去就会发现它的套路和中序后序构造几乎一模一样找根、切区间、递归左右。唯一的区别是这里找根的方式不是从后序数组里取最后一个元素而是要在当前区间里扫描一遍找最大值。def constructMaximumBinaryTree(nums: List[int]) - TreeNode: def build(left, right): if left right: return None max_idx left for i in range(left 1, right): if nums[i] nums[max_idx]: max_idx i node TreeNode(nums[max_idx]) node.left build(left, max_idx) node.right build(max_idx 1, right) return node return build(0, len(nums))每次找最大值都要线性扫描当前区间所以整体时间复杂度是 O(n²)最坏情况下数组有序时表现最差。但通过这道题是绰绰有余的。3.2 参数设计的决定性作用不要把切片当后路这题最常见的入门写法是每次递归把数组切成nums[:max_idx]和nums[max_idx1:]然后传给下一层。这种切片写法在本地能跑评测也能过但有一个很现实的问题每次切片都会复制一个数组空间开销叠加起来很可观。更重要的是切片的写法把当前子树在原始数组上的范围这个信息藏了起来代码可读性反而不如传边界参数。我自己的习惯是构造类题目的递归函数一律设计成原始数组引用 左右边界的形式。这样递归的每一层都能清楚地知道自己在处理哪一段后面遇到有序数组转二叉搜索树、线段树这类题目写起来风格也是统一的。传边界参数还有一个附带好处方便调试。你可以随时在递归入口打印 left 和 right清楚地看到区间是怎么一层层缩小的哪一步边界算错了一眼就能找出来。切片版本想打印我在处理哪一段就不那么直观了。3.3 彩蛋最大二叉树可以用单调栈一趟构建区间法是最直观的解法但如果你已经写熟了可以了解一个进阶版本单调栈一趟构建时间复杂度降到 O(n)。核心思路是从左到右扫描数组维护一个单调递减栈。当前元素大于栈顶元素时不断出栈最后一个出栈的节点会成为当前元素的左孩子如果当前元素小于栈顶则栈顶的右孩子指向当前元素。扫描结束后栈底就是整棵树的根。def constructMaximumBinaryTree(nums: List[int]) - TreeNode: stack [] for num in nums: node TreeNode(num) while stack and stack[-1].val num: node.left stack.pop() if stack: stack[-1].right node stack.append(node) return stack[0]第一次看这段代码可能会觉得这个写法怎么能对。我当时也反复验证了很久才想明白当前元素是它所在区间的最大值所有比它小且已经出栈的节点在最终树里一定都在它的左侧并且会挂在它的左孩子路径上。这个逻辑是最大二叉树定义的自然推论。不过实话实说面试时能用区间法清晰讲出来已经足够单调栈属于锦上添花的扩展不用强求第一次就吃透。4. 合并二叉树两个树同时递归的正确打开方式4.1 空节点提前返回合并二叉树的第一准则合并二叉树的规则很简单两棵树相同位置的节点值相加如果某一侧只有一棵树有节点直接接上那棵树的节点。递归出口是这道题的灵魂。def mergeTrees(root1: TreeNode, root2: TreeNode) - TreeNode: if not root1: return root2 if not root2: return root1 node TreeNode(root1.val root2.val) node.left mergeTrees(root1.left, root2.left) node.right mergeTrees(root1.right, root2.right) return node注意这里的出口设计root1 为空直接返回 root2root2 为空直接返回 root1。这样后续递归就不需要再判断空的情况了左右子树递归的时候哪怕传进去一个空节点也能被这个出口正常兜住。很多初学者会写出一堆分支判断如果两个都不为空怎么办如果一个为空一个不为空怎么办。这样写逻辑上没错但代码会变得又臭又长。用空节点提前返回的思想所有分支都被压缩成了两个出口条件递归体一下子干净很多。这里也体现了一个通用的递归设计思想终止条件要尽量把不需要当前层处理的情况全部挡在递归入口。处理得越干净单层逻辑就越简单。4.2 复用原树还是新建树先问清楚需求上面这版代码默认是可以修改原树的直接把 root1 和 root2 的值加在一起建新节点子树也直接复用原树的节点。这在大多数在线评测平台是允许的。但如果题目明确要求不能修改原树那情况就不一样了。尤其是当一边子树为空时需要把另一边的子树完整复制出来而不是直接返回原节点。这种深拷贝式的写法在面试中不常见但一旦被问到最好能答出来。我的建议是做题之前先确认题意——是否允许修改输入数据。这不仅是代码洁癖问题而是很多题目解法的选择分岔口。允许修改输入代码可以非常简洁不允许修改就要在一开始设计递归函数时就考虑复制逻辑而不是后面补救。这类两棵树同时递归的问题还有一个常见错误递归调用时把左右子树传反了。比如mergeTrees(root1.left, root2.right)这种错误在节点不多的时候可能根本暴露不出来因为树结构不对称时结果也是错的但很难肉眼察觉。我写这种题目时每次递归调用的成对参数都会下意识检查一遍左右方向。4.3 合并类问题的变形方向合并二叉树这个基础模板能延伸出不少场景两棵树做交集、在合并过程中统计节点值差异、合并后判断是否平衡等。核心都是同时递归两棵树的同位置节点。把这个模板理解到位之后你会发现它在二叉搜索树相关题目里也有应用。比如后续会遇到两棵二叉搜索树的所有元素这类题目虽然解法是先中序遍历再合并有序数组但同时处理两棵树这个思维是共通的。先把这个两路递归的手感练出来后面刷题会轻松一些。5. 这一篇做完我总结的二叉树递归套路5.1 用这一篇的题复盘递归三部曲老生常谈的递归三部曲只有在具体题目里对照着用才能真正变成自己的东西。这一篇的几道题正好是绝佳样本。先看参数和返回值。路径总和返回布尔值因为找到一条就提前结束路径总和II不返回值因为要收集所有路径中序后序构造返回 TreeNode因为要把子树层层组装给上一层合并二叉树也返回 TreeNode因为要把合并结果往上传递。再看终止条件。路径总和在叶子节点停下构造类题目在区间为空时停下合并二叉树在某一方为空时停下。最后看单层逻辑。路径总和做targetSum - node.val的递减和 or 合并构造类题目先找根再切区间合并二叉树先把两个根节点值相加再递归左右。我把这些整理成一个表格方便日后复习时快速回忆题目递归返回值终止条件单层核心操作路径总和bool叶子节点targetSum - node.val路径总和II无叶子节点收集路径中序后序构造TreeNode区间为空找根、切区间最大二叉树TreeNode区间为空找最大值下标合并二叉树TreeNode一方为空根节点值相加5.2 路径类题目最容易漏掉的一步恢复现场如果你选择写显式回溯而不是路径拷贝那么恢复现场是路径类题目最容易翻车的地方。我见过不少类似的错误写法def dfs(node, target, path): if not node: return path.append(node.val) if not node.left and not node.right and sum(path) target: res.append(path[:]) # 这里必须拷贝 dfs(node.left, target, path) dfs(node.right, target, path) path.pop()如果res.append(path)没加拷贝结果是灾难性的path 在递归返回的过程中不断 pop最终 res 里的所有路径都会变成空列表。这个错误很难用眼睛发现因为调试时你看到 res 里确实有数据但那只是还没被回溯清空的假象。一个实用的习惯是只要在递归里用到了共享的可变列表每次加入结果时都要问自己一句——这个列表之后还会不会被修改会就拷贝。这个习惯能帮你省掉大量查 bug 的时间。5.3 构造类题目的自查方法构造类题目写完怎么验证我有一个很笨但很管用的方法写两个辅助函数把构造出来的树分别做一遍前序遍历和中序遍历看看能不能还原出原始数组。def preorder(root): if not root: return [] return [root.val] preorder(root.left) preorder(root.right) def inorder(root): if not root: return [] return inorder(root.left) [root.val] inorder(root.right)对中序后序构造的题构造完之后做一次中序遍历如果结果和原始中序数组完全一致说明根的定位和区间切分大概率没问题。对最大二叉树做一次前序遍历检查根是不是每次都出现在正确的位置。这个方法虽然朴素但在本地调试时比肉眼盯变量高效得多。构造类题目最容易出的是边界错误比如区间端点差了 1这种问题靠读代码很难发现一跑辅助函数立刻现行。最后说一点实际体会。二叉树刷到十五篇这个阶段很多人会觉得怎么又是递归但递归真正的难点从来不是会不会写而是怎么控制递归的走向和边界。这一篇反复强调的三件事——返回值设计、区间开闭约定、共享变量的拷贝与恢复——是递归三件套里最实用的三个抓手。我自己在写构造类题目前一定会先在纸上把中序和后序的切分过程画一遍至少画到第二层递归。这个习惯帮我少调了无数个小时的 bug。如果你也在这一篇卡住不妨停下来选一个例子手动展开到第二层递归很多边界问题都会瞬间变得清楚。