刷题刷到二叉树这一章构造二叉树几乎是绕不开的一组题。很多人遍历背得很熟前序中序后序随手一写就过可一碰到给定两个遍历序列还原整棵树就懵了。我Day 17那天集中把这类题刷了一遍从经典的前序中序构造到中序后序、最大二叉树、合并二叉树刷完最大的感受是它们其实是同一道题核心就三个字——找根、切分、递归。这篇文章就围绕构造二叉树这条主线把我当天总结的套路、代码模板、边界条件和踩过的坑完整写一遍。适合刚学完二叉树遍历、想突破构造类题目的朋友也适合面试前想快速过一遍这类题的人。放心只要你把前序/中序/后序遍历的基本概念搞清楚了剩下就是套模板的事。1. 构造二叉树先理解一个核心问题1.1 为什么前序中序能唯一确定一棵树要说清楚构造二叉树的本质得先回答一个问题给定哪些遍历序列能唯一还原出一棵二叉树答案中最常见也最实用的组合就是前序遍历 中序遍历。原因很简单前序遍历的第一个节点必然是整棵树的根节点而在中序遍历序列中根节点左边的所有节点都属于左子树右边的所有节点都属于右子树。于是我们拿到了两个关键信息根是谁、左右子树各包含哪些节点。有了这个信息事情就变成了一个递归过程。对左子树来说它的前序遍历序列也能从原始前序序列中切出来中序遍历序列也能切出来于是又回到了前序中序还原一棵子树这个问题上。一层层切下去整棵树就被还原出来了。那为什么前序后序通常不行举个最简单的反例二叉树只有两个节点根节点为1子节点为2。前序遍历都是[1, 2]后序遍历都是[2, 1]但 2 到底是 1 的左孩子还是右孩子完全无法判断。简单说没有中序序列就缺少了哪些节点在左、哪些节点在右的信息树形就确定不下来。1.2 构造题的底层套路找到根切分递归如果你把所有构造二叉树的题放在一起看会发现套路高度统一可以总结成一个三步走找根从前序/后序/最大值中找到当前子树的根节点。切分用中序序列或区间信息把左右子树对应的节点区间分开。递归对左区间和右区间分别重复上述过程。这三步里最难也最容易出错的不是找根而是切分。因为切分涉及区间下标的计算一旦索引写错整个递归就乱了。后面我会详细拆这个点。另外要强调一点树的定义本身就是递归的所以这类题用递归写几乎是最自然的选择。你不需要去想整棵树怎么还原只需要想清楚当前这一个根节点怎么处理左右子树怎么交给递归就够了。1.3 三种遍历组合的可行性对照为了把哪些组合能唯一确定二叉树这件事彻底讲清楚我整理了下面这个表格平时复习也可以直接拿它当速查表遍历组合能否唯一确定原因简述前序 中序能前序确定根中序划分左右子树中序 后序能后序确定根中序划分左右子树前序 后序通常不能缺少中序信息左右子树划分不唯一前序 后序二叉树为满二叉树时能满二叉树每个节点要么有两个孩子要么没有孩子左右划分可由后序左子树的位置推出所以面试里最常见的还是前序中序和中序后序两种。前序后序虽然不能唯一确定一般二叉树但如果在题目里额外说明了是满二叉树反而可以构造这个可以作为延伸了解。2. 主菜从前序与中序遍历序列构造二叉树2.1 算法流程的关键步骤拆解直接拿力扣 105 题当例子。假设给定的前序遍历和中序遍历分别是preorder [3, 9, 20, 15, 7]inorder [9, 3, 15, 20, 7]手动推一遍流程前序第一个元素是3所以根节点是3。在中序里找到3它左边是[9]右边是[15, 20, 7]。这说明左子树只有节点9右子树有15、20、7三个节点。左子树大小为 1所以在 preorder 中3后面紧跟的[9]就是左子树的前序遍历剩下的[20, 15, 7]是右子树的前序遍历。对左子树和右子树分别递归。这个过程里最关键的一步是第三步根据左子树的大小切出左右子树各自的前序遍历区间。很多人就是在这里把索引写错的。2.2 用哈希表把查找从 O(n) 变成 O(1)每轮递归都需要在中序序列里定位根节点的位置。如果每次都线性扫描一次每一层递归的复杂度是 O(n)递归总层数也是 O(n)整体会退化到 O(n²)当 n 到 5000 以上时性能就明显撑不住了。解决办法很直接在做递归之前先把中序序列里每个值对应的下标存进哈希表Python 里就是字典。之后每次找根直接查表 O(1) 拿到下标。这个优化写起来不超过三行但整体复杂度从 O(n²) 降到 O(n)属于性价比极高的操作。我第一次写这道题时偷懒没用哈希表靠inorder.index(root_val)硬找结果一提交数据量大的用例直接超时。从那以后凡是需要频繁在中序序列中定位的题我都会先建一张值到下标的映射表。2.3 代码实现与参数解释这一步给出我最终稳定通过的写法采用的是左闭右开区间也就是区间[left, right)包含left不包含right。这个约定可以避免很多边界错误。from typing import List, Optional class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) - Optional[TreeNode]: # 用哈希表记录中序序列中每个值的下标 idx_map {val: idx for idx, val in enumerate(inorder)} def dfs(pre_left, pre_right, in_left, in_right): # 空区间说明当前子树没有节点 if pre_left pre_right: return None # 前序的第一个元素是当前子树的根 root_val preorder[pre_left] root TreeNode(root_val) # 在中序中找到根的位置并计算左子树大小 in_root idx_map[root_val] left_size in_root - in_left # 左子树前序区间 (pre_left1, pre_left1left_size) root.left dfs(pre_left 1, pre_left 1 left_size, in_left, in_root) # 右子树前序区间 (pre_left1left_size, pre_right) root.right dfs(pre_left 1 left_size, pre_right, in_root 1, in_right) return root n len(preorder) return dfs(0, n, 0, n)递归函数dfs有四个参数前序区间的左右端点、中序区间的左右端点。写的时候心里要非常清楚每个参数代表的意义否则很容易把左右端点传反。left_size in_root - in_left是核心计算。因为在中序区间[in_left, in_root)内全部都是左子树节点所以用根的位置 - 左边界就能得到左子树的大小。有了left_size前序序列里左右子树的切分就水到渠成了。2.4 区间写法的一个小技巧很多人在写这类题时一会儿用左闭右闭一会儿用左闭右开代码稍长就乱了。我的建议是从头到尾统一用左闭右开理由有两点第一空区间的判断非常统一left right就是空不需要额外写left right这种带等号与否的双重判断第二划分区间时不容易丢节点因为[in_left, in_root)天然表示左子树右子树直接从in_root 1开始不需要纠结右边界到底要不要加一。这个约定一开始可能不太习惯但写两三道题之后就顺手了。后面中序后序、最大二叉树这些题目我全部沿用左闭右开一次都没再在边界上报错过。3. 同套思路三道变式题连刷3.1 从中序与后序遍历序列构造二叉树这道题106 题和 105 题几乎完全对称唯一的区别是根节点的位置变了。前序遍历时根在最前面而后序遍历时根在最后面所以取根的方式从preorder[pre_left]变成了postorder[post_right - 1]。核心逻辑完全一致用根在中序里的位置算出左子树大小然后切分中序区间和后序区间递归构建左右子树。代码写出来是这样的from typing import List, Optional class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) - Optional[TreeNode]: idx_map {val: idx for idx, val in enumerate(inorder)} def dfs(post_left, post_right, in_left, in_right): if post_left post_right: return None # 后序的最后一个元素是根 root_val postorder[post_right - 1] root TreeNode(root_val) in_root idx_map[root_val] left_size in_root - in_left # 左子树后序区间 (post_left, post_left left_size) root.left dfs(post_left, post_left left_size, in_left, in_root) # 右子树后序区间 (post_left left_size, post_right - 1) root.right dfs(post_left left_size, post_right - 1, in_root 1, in_right) return root n len(inorder) return dfs(0, n, 0, n)对比一下两道题差别其实就是两行取根的位置以及右子树的右边界在post_right - 1因为已经拿掉根了。剩下的全部一样。所以你会看到构造二叉树这类题目真正要记的模板其实就一套剩下的都是微调。3.2 最大二叉树找最大值当根力扣 654 题最大二叉树。题目给一个数组要求构造一棵二叉树数组中的最大值是根最大值左边的子数组构建左子树右边的子数组构建右子树。看到最大值是根、左边左子树、右边右子树就会发现这就是模板里的找根 切分过程只是这里没有前序和后序而是直接在数组上操作。代码如下from typing import List, Optional class Solution: def constructMaximumBinaryTree(self, nums: List[int]) - Optional[TreeNode]: if not nums: return None max_val max(nums) max_idx nums.index(max_val) root TreeNode(max_val) root.left self.constructMaximumBinaryTree(nums[:max_idx]) root.right self.constructMaximumBinaryTree(nums[max_idx 1:]) return root这个写法最直观逻辑最短适合用来理解找根-切分-递归的过程。但它有两个小问题一是每次max和index都要遍历子数组整体复杂度最坏是 O(n²)二是每次切片nums[:max_idx]都会生成新数组有额外空间开销。如果想优化可以改成传下标的写法让递归始终在原数组上处理区间不再产生新数组。这也是为什么我建议从一开始就练下标版的原因。刷题初级阶段用切片版没问题但到了追求性能或者笔试环境里下标版更稳。另外提一个进阶点最大二叉树还有一种线性复杂度的解法借助单调栈来构建。它利用二叉树是笛卡尔树这个性质可以在 O(n) 时间内构建整棵树。平时练习可以了解一下但面试如果要求写这道题递归版本已经足够。3.3 合并二叉树递归处理两个根力扣 617 题合并二叉树。给定两棵树要求把对应位置的节点值相加如果某个位置只有一棵树有节点就直接把那边的节点拿过来。这道题表面上和前序中序构造不同但骨子里还是递归。你可以把它理解成同时遍历两棵树在每一层处理当前根节点的合并再把左右子树合并的结果挂回去。from typing import Optional class Solution: def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) - Optional[TreeNode]: if not root1: return root2 if not root2: return root1 root TreeNode(root1.val root2.val) root.left self.mergeTrees(root1.left, root2.left) root.right self.mergeTrees(root1.right, root2.right) return root这里最需要注意的就是两个终止条件如果某一棵树的当前节点为空直接返回另一棵树的节点。这样做既处理了空节点没有子节点的情况也顺便把整棵非空子树复制过去了不需要再逐层展开。我一开始写这道题时还在纠结如果两个节点都非空要不要 new 一个新节点。试了几次之后发现按上面的写法每次都 new 才是最稳妥的因为不能直接修改原树有的题目不允许破坏输入。如果你确定可以原地改树那直接改 root1 也完全可以代码会更短但可读性会差一点。4. 构造二叉树常见报错与排查技巧4.1 高频错误的四个来源这类题的错误非常有规律我把刷题阶段遇到的高频问题整理成了速查表错误类型具体表现解决办法递归终止条件漏写栈溢出或无限递归进入函数后先判断区间是否为空left right时返回 None区间开闭约定混用节点丢失或重复全程统一左闭右开不接受临时切换左右子树索引写错重建出来的树乱套画出区间图标注每个索引的含义后再写代码用切片导致超时大数据量用例 TLE改用下标法避免每次递归新建数组根节点定位方式错误比如后序题错用第一个元素当根前序取左端后序取右端-1最大二叉树取区间最大值这里重点说一下区间开闭约定混用的问题。人在紧张的时候很容易上一行还写着[left, right)下一行就顺手写成right - 1套进左闭右闭的逻辑里。这种错误排查起来特别费时间因为你很难一眼看出哪一行用错了。我的做法是在写递归函数的第一行把区间含义用注释写明比如# 左闭右开 [pre_left, pre_right)这样至少能减少一半的混淆。4.2 用最小用例自测写完代码后别急着提交。先在心智里构造几个最小用例跑一遍比反复提交省时间得多空树preorder []inorder []应该返回None。单节点树preorder [1]inorder [1]应该返回只有一个根节点的树。只有左子树preorder [1, 2]inorder [2, 1]。只有右子树preorder [1, 2]inorder [1, 2]。这几个用例基本覆盖了所有边界情况。只要它们能过代码的整体框架就没有问题剩下的逻辑错误可以通过打印调试来定位。尤其推荐只有左子树和只有右子树这两个对称用例。很多人在写右子树区间时会把右边界算错这两个用例可以一针见血地暴露问题。4.3 调试技巧打印参数和层序验证如果用例没过我一般会先打印递归函数的四个参数看看每一层传入的区间是否合理。比如构建前序中序时打印(pre_left, pre_right, in_left, in_right)能非常直观地发现左子树区间越界了还是右子树为空了这类问题。还有一种验证方式更保险把构建出来的树做一次层序遍历和原始数据的结构对比。层序遍历能清晰展示每个节点的父子关系如果树结构有问题一眼就能看出来。比如你原本期望的是根 3 的左孩子是 9结果层序遍历打印出来左孩子成了 20那就说明切分逻辑有问题。一个小技巧调试用的打印函数不要随便删除先用注释包起来等整个题解完全通过后再清理。因为调下一道变式题时很可能又要用到同样的打印逻辑。5. 额外心得与后续扩展5.1 手撕这类题的建议节奏如果你正在刷题我建议构造二叉树这类题不要只做一遍。我的节奏是这样的第一遍看题解把前序中序这道模板题彻底理解透能做到手写出来第二遍不看任何参考自己写中序后序那道题写完以后再写最大二叉树第三天再回头把这三道题快速重写一遍。为什么要隔一天重写因为构造题的代码量不大很多人当天写完就背住了但隔一天再写才能真正检验自己是不是理解了递归区间怎么切这件事。实测下来只要第三遍还能独立写出来这组题基本就焊死在脑子里了。5.2 构造思路能延伸到哪些场景掌握找根-切分-递归之后很多二叉树问题突然就变得很简单了。比如搜索二叉树BST的构造给定 BST 的前序遍历因为 BST 的左子树都小于根、右子树都大于根所以可以只用一个前序序列配合上下界约束来完成构造。二叉树的序列化与反序列化把二叉树变成字符串再变回来本质上也是在还原树的结构常用前序遍历 空节点标记。根据遍历序列判断合法性比如判断一个给定的前序序列能否构成合法的 BST这类问题也是基于同样的切分思想只是多了一层合法性检查。所以构造二叉树不只是一道孤立题目它背后是如何用递归处理树结构这一大类的代表。把这道题吃透收益远超题目本身。5.3 我踩过的几个真实教训最后闲聊几句个人的踩坑总结。我第一次写 105 题时用的是切片法每层递归都preorder[1:left_size1]、inorder[:in_root]这样切来切去。代码短是短但运行效率很差而且因为每次切片都重新生成数组递归里传的参数越来越多整个人很快就被绕晕了。后来我强迫自己把所有题都改成下标写法痛苦了大概两三道题之后就彻底通了。现在我写任何构造类题目都会先想清楚区间开闭约定再动手。另一个教训是变量命名尽量带上 in 和 pre 的前缀别用l1、r1、l2、r2这种。第一次图省事用短变量名结果调试了半小时全是复制粘贴导致传参顺序搞反。老老实实用pre_left、pre_right、in_left、in_right代码可读性高自己也省心。如果你正在刷到这里别怕这类题。先把模板题啃下来再用变式题反复练切分逻辑一天之内就能形成肌肉记忆。后面再遇到构造二叉树的题目你会发现在所有二叉树题型里它反而是最不需要动脑子的那一类。