剑指 Offer 07：从前序与中序遍历序列重建二叉树（分治法详解）

剑指 Offer 07：从前序与中序遍历序列重建二叉树（分治法详解）

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

本文基于 LeetCode-Book 仓库中《剑指 Offer》章节的题目文档 剑指 Offer 07. 重建二叉树，系统讲解"由前序 + 中序遍历序列重建二叉树"这一经典递归问题的解题思路。读完本文，你将掌握利用前序遍历定位根节点、中序遍历划分左右子树的核心推论，能熟练套用"分治算法"的三要素（递推参数、终止条件、递推工作）编写递归代码，并理解哈希表优化带来的 O(N) 时间复杂度原理，最终可以独立推导并写出 Python / Java / C++ 三语言实现。

问题背景与解题思路

本题（对应 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal）要求根据一棵二叉树的前序遍历preorder与中序遍历inorder，构造并返回这棵二叉树。

解题的关键在于两种遍历方式的本质性质：

• 前序遍历性质：节点按照[ 根节点 | 左子树 | 右子树 ]排序；
• 中序遍历性质：节点按照[ 左子树 | 根节点 | 右子树 ]排序。

以题目示例为例（前序为[3, 9, 20, 15, 7]，中序为[9, 3, 15, 20, 7]）：

• 前序遍历划分[ 3 | 9 | 20 15 7 ]
• 中序遍历划分[ 9 | 3 | 15 20 7 ]

由这两个划分可得出三条核心推论：

1. 前序遍历的首元素为树的根节点node的值；
2. 在中序遍历中搜索根节点node的索引，可将中序遍历划分为[ 左子树 | 根节点 | 右子树 ]；
3. 根据中序遍历中左（右）子树的节点数量，可将前序遍历划分为[ 根节点 | 左子树 | 右子树 ]。

通过以上三步，可以确定三个节点：树的根节点、左子树根节点、右子树根节点。

根据「分治算法」思想，对于树的左、右子树，仍可复用以上方法进一步划分子树的左右子树——整个重建过程就是这样一层层递归展开的。

分治算法解析

把上述推论形式化，递归函数recur(root, left, right)的三个要素如下：

• 递推参数：根节点在前序遍历的索引root、子树在中序遍历的左边界left、子树在中序遍历的右边界right；

• 终止条件：当left > right，代表已经越过叶节点，此时返回null（空子树）；

• 递推工作：

  1. 建立根节点node：节点值为preorder[root]；
  2. 划分左右子树：查找根节点在中序遍历inorder中的索引i。为了提升效率，使用哈希表dic存储中序遍历"值 → 索引"的映射，使查找操作的时间复杂度降为 O(1)；
  3. 构建左右子树：开启左右子树的递归，边界取值规则如下表：

  根节点索引	中序遍历左边界	中序遍历右边界
  左子树	root + 1	left	i - 1
  右子树	i - left + root + 1	i + 1	right

  TIPS：右子树根节点索引i - left + root + 1的含义是根节点索引 + 左子树长度 + 1——因为在当前子树的前序序列中，左子树紧随根节点之后，其长度恰好等于中序遍历中i - left。

• 返回值：回溯返回node，作为上一层递归中根节点的左 / 右子节点。

示例递归过程推演

以下用题目示例手工推演前几层递归，帮助理解参数是如何演化的：

1. recur(0, 0, 4)：preorder[0] = 3建根节点，中序中3的索引i = 1；
   • 左子树：recur(0 + 1, 0, 1 - 1)=recur(1, 0, 0)，重建节点9（left == right，无左右子树，回溯）；
   • 右子树：recur(1 - 0 + 0 + 1, 1 + 1, 4)=recur(2, 2, 4)，preorder[2] = 20建节点，中序中20的索引i = 3；
     • 左子树：recur(3, 2, 2)，重建节点15；
     • 右子树：recur(4, 4, 4)，重建节点7。
2. 全部回溯完成后，得到的树形结构即：

3 / \ 9 20 / \ 15 7

每一层递归都严格对应"先建根、再分左右"的过程，直到left > right触发终止条件，递归自叶向根逐层回溯拼接完成整棵树。

三语言代码实现与仓库源码印证

仓库中 Python、Java、C++ 三个版本的实现与文档中的算法一一对应，测试用例均为前序[3, 9, 20, 15, 7]、中序[9, 3, 15, 20, 7]，驱动代码通过各自的print_tree/PrintUtil.printTree工具函数（定义于 print_util.py 等）打印重建后的树形结构：

• Python 版：sfo_07_reconstruct_binary_tree_s1.py
• Java 版：sfo_07_reconstruct_binary_tree_s1.java
• C++ 版：sfo_07_reconstruct_binary_tree_s1.cpp

Python 实现

class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: def recur(root, left, right): if left > right: return # 递归终止 node = TreeNode(preorder[root]) # 建立根节点 i = dic[preorder[root]] # 划分根节点、左子树、右子树 node.left = recur(root + 1, left, i - 1) # 开启左子树递归 node.right = recur(i - left + root + 1, i + 1, right) # 开启右子树递归 return node # 回溯返回根节点 dic, preorder = {}, preorder for i in range(len(inorder)): dic[inorder[i]] = i return recur(0, 0, len(inorder) - 1)

仓库中 TreeNode 节点类提供val、left、right三个字段，与 LeetCode 官方定义一致；Python 版利用闭包共享外部dic哈希表与preorder数组，避免在递归签名中额外传参。

Java 实现

class Solution { int[] preorder; HashMap<Integer, Integer> dic = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; for(int i = 0; i < inorder.length; i++) dic.put(inorder[i], i); return recur(0, 0, inorder.length - 1); } TreeNode recur(int root, int left, int right) { if(left > right) return null; // 递归终止 TreeNode node = new TreeNode(preorder[root]); // 建立根节点 int i = dic.get(preorder[root]); // 划分根节点、左子树、右子树 node.left = recur(root + 1, left, i - 1); // 开启左子树递归 node.right = recur(i - left + root + 1, i + 1, right); // 开启右子树递归 return node; // 回溯返回根节点 } }

从 Java 版源码结构看，preorder与dic被提升为Solution的成员变量，递归方法recur直接读写它们，与 Python 闭包的思路等价，只是组织形式不同。

C++ 实现

class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { this->preorder = preorder; for(int i = 0; i < inorder.size(); i++) dic[inorder[i]] = i; return recur(0, 0, inorder.size() - 1); } private: vector<int> preorder; unordered_map<int, int> dic; TreeNode* recur(int root, int left, int right) { if(left > right) return nullptr; // 递归终止 TreeNode* node = new TreeNode(preorder[root]); // 建立根节点 int i = dic[preorder[root]]; // 划分根节点、左子树、右子树 node->left = recur(root + 1, left, i - 1); // 开启左子树递归 node->right = recur(i - left + root + 1, i + 1, right); // 开启右子树递归 return node; // 回溯返回根节点 } };

C++ 版将递归辅助函数recur声明为private成员，哈希表使用unordered_map<int, int>，其余逻辑与 Java 版完全一致。

注意：本文方法只适用于"无重复节点值"的二叉树——哈希表以节点值为键建立映射的前提是值唯一，若存在重复值则无法确定根节点在中序中的确切位置。

复杂度分析

• 时间复杂度 O(N)：其中 N 为树的节点数量。初始化哈希表dic需遍历inorder，占用 O(N)；递归共建立 N 个节点，每层递归中的节点建立、哈希查找操作占用 O(1)，因此总计使用 O(N) 时间。
• 空间复杂度 O(N)：哈希表使用 O(N) 额外空间；最差情况下（输入二叉树退化为链表时），递归深度达到 N，占用 O(N) 的栈帧空间；因此总共使用 O(N) 空间。

小结与延伸

本题的标准解法可以概括为一句话：前序定根、中序定界。掌握以下要点即可复用到同类题目：

1. 前序遍历首元素恒为当前子树的根，这是"分而治之"的切分依据；
2. 中序遍历中根索引i把序列切成左、右两段，i - left即左子树长度，用于推算右子树在前序中的起始索引i - left + root + 1；
3. 用哈希表把"值 → 中序索引"的查找降为 O(1)，是整题达到 O(N) 时间复杂度的关键；
4. 递归终止条件left > right精确对应"空子树"，保证叶节点之后不再越界。

延伸方向：若题目只给"前序 + 后序遍历"（LeetCode 889），后序中除根外的首元素对应左子树最左侧节点，重建时只能假定"左子树为空"等退化情形；若树是二叉搜索树，则只凭前序或中序其一即可唯一重建（如 LeetCode 1008）。本题与 剑指 Offer 07. 重建二叉树 对应的完整代码及测试用例均已收录在仓库的sword_for_offer/codes目录下，可按上文给出的三个语言文件路径直接查看、编译与运行验证。

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book