教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载给定一棵二叉树的前序遍历与中序遍历结果能否唯一地还原出这棵二叉树并输出它的根结点这是面试中最高频的树类算法题之一剑指 Offer 第 7 题 / LeetCode 105也是理解递归分治思想的最佳入口。本篇以 YCBlogs 仓库中 leetcode/05.树/11.重建二叉树2.md 的题目与代码为骨架结合仓库中二叉树遍历、存储与链表的系列笔记完整讲解重建原理、可运行的 Java 实现、合法性校验以及基于哈希表的优化版本帮助读者从“背代码”进阶到“理解每一步下标推导”。01. 题目要求原题描述如下输入某二叉树的前序遍历和中序遍历的结果请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}重建二叉树并输出它的头结点。关键约束有两个前序、中序两种遍历结果必须来自同一棵树序列中不含重复数字重复数字会导致中序中无法唯一确定根结点位置重建结果不再唯一。这句话正是整个算法的“合法输入前提”后面实例代码中会看到针对非法输入的防御性处理。姊妹篇 leetcode/05.树/10.重建二叉树1.md 记录了同一道题的另一种写法使用 HashMap 缓存中序索引两种写法会在下文对比讲解。02. 前置知识三种遍历方式要理解重建原理必须先明确二叉树三种遍历的定义。仓库中 leetcode/05.树/02.实现二叉树.md 给出了规范表述前序遍历对于树中任意节点先打印这个节点再打印它的左子树再打印它的右子树中序遍历对于树中任意节点先打印左子树再打印它本身最后打印右子树后序遍历对于树中任意节点先打印左子树再打印右子树最后打印它本身。也就是说“前、中、后”描述的是当前结点相对其左右子树的访问顺序。以前序遍历为例private void preOrder(BSTNodeT tree) { if(tree ! null) { System.out.print(tree.key ); preOrder(tree.left); preOrder(tree.right); } }中序遍历与后序遍历只需调整三行代码的顺序即可完整实现可参考 leetcode/05.树/02.实现二叉树.md。由定义可以得到两个对重建至关重要的结论前序遍历的第一个元素一定是整棵树的根结点中序遍历中根结点把序列分成两部分左边是左子树的中序结果右边是右子树的中序结果。这正是重建算法的全部理论基础。关于二叉树的基本性质第 i 层最多 $2^{i-1}$ 个结点、深度为 k 的二叉树至多有 $2^k-1$ 个结点等可参阅 leetcode/05.树/01.二叉树简介.md。03. 问题分析递归分治思想原文档的分析非常精炼一句话概括了整个算法由前序遍历的第一个节点可知根节点。根据根节点可以将中序遍历划分成左右子树。在前序遍历中找出对应的左右子树其第一个节点便是根节点的左右子节点。按照上述方式递归便可重建二叉树。下面用题目的例子逐步拆解前序 1 2 4 7 3 5 6 8 中序 4 7 2 1 5 3 8 6第 1 步确定根前序第一个元素是1所以根结点值为1。第 2 步划分中序在中序中定位1其下标为 3中序 4 7 2 [1] 5 3 8 6 └ 左子树 ┘ └ 右子树 ┘左边{4, 7, 2}是左子树的中序遍历共 3 个元素右边{5, 3, 8, 6}是右子树的中序遍历共 4 个元素。第 3 步切分前序因为左右子树元素个数确定前序中紧随根之后的前 3 个元素{2, 4, 7}就是左子树的前序剩余{3, 5, 6, 8}是右子树的前序前序 1 [2 4 7] [3 5 6 8] 根 └ 左子树┘ └ 右子树 ┘第 4 步递归对左子树前序{2,4,7} 中序{4,7,2}和右子树前序{3,5,6,8} 中序{5,3,8,6}重复第 13 步即可得到整棵树。每递归一层问题规模就缩小到一棵子树当序列区间为空时递归终止。这正是典型的分治思想大问题分解为结构相同的子问题通过递归自底向上组装。04. 实例代码区间下标递归版原文档给出了完整的可运行 Java 实现。代码包含两个重载方法外层方法负责参数合法性校验内层方法负责真正的递归重建。以下为原文代码已补充必要注释public class Test { /** * 二叉树节点类 */ public static class BinaryTreeNode { int value; BinaryTreeNode left; BinaryTreeNode right; } /** * 输入某二叉树的前序遍历和中序遍历的结果请重建出该二叉树。 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 * * param preorder 前序遍历 * param inorder 中序遍历 * return 树的根结点 */ public static BinaryTreeNode construct(int[] preorder, int[] inorder) { // 输入的合法性判断两个数组都不能为空并且都有数据而且数据的数目相同 if (preorder null || inorder null || preorder.length ! inorder.length || inorder.length 1) { return null; } return construct(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); } /** * 递归重建二叉树 * * param preorder 前序遍历 * param ps 前序遍历的开始位置 * param pe 前序遍历的结束位置 * param inorder 中序遍历 * param is 中序遍历的开始位置 * param ie 中序遍历的结束位置 * return 树的根结点 */ public static BinaryTreeNode construct(int[] preorder, int ps, int pe, int[] inorder, int is, int ie) { // 开始位置大于结束位置说明已经没有需要处理的元素了 if (ps pe) { return null; } // 取前序遍历的第一个数字就是当前的根结点 int value preorder[ps]; int index is; // 在中序遍历的数组中找根结点的位置 while (index ie inorder[index] ! value) { index; } // 如果在整个中序遍历的数组中没有找到说明输入的参数是不合法的抛出异常 if (index ie) { throw new RuntimeException(Invalid input); } // 创建当前的根结点并且为结点赋值 BinaryTreeNode node new BinaryTreeNode(); node.value value; // 递归构建当前根结点的左子树左子树的元素个数index-is1个 // 左子树对应的前序遍历的位置在[ps1, psindex-is] // 左子树对应的中序遍历的位置在[is, index-1] node.left construct(preorder, ps 1, ps index - is, inorder, is, index - 1); // 递归构建当前根结点的右子树右子树的元素个数ie-index个 // 右子树对应的前序遍历的位置在[psindex-is1, pe] // 右子树对应的中序遍历的位置在[index1, ie] node.right construct(preorder, ps index - is 1, pe, inorder, index 1, ie); // 返回创建的根结点 return node; } }4.1 外层方法合法性校验外层construct(int[] preorder, int[] inorder)主要做四件事preorder null前序为空直接返回nullinorder null中序为空直接返回nullpreorder.length ! inorder.length两个序列长度不一致不可能来自同一棵树inorder.length 1长度为 0 的空树返回null。只有通过校验才会进入真正的递归。这一层防御是面试加分项——很多候选人只写递归却忽略了对“输入本身就是错误数据”的处理。4.2 内层方法核心下标推导内层方法只维护四个区间下标ps、pe、is、ie不复制数组全程在原数组上操作终止条件ps pe表示前序区间已空说明该子树不存在返回null。取根value preorder[ps]前序区间第一个元素即当前子树的根。定位在中序区间[is, ie]中线性查找value找到后记录index。若index ie说明整个中序区间都没有该值输入序列不合法抛出RuntimeException(Invalid input)。左子树左子树元素个数 index - is中序区间[is, index-1]的长度左子树前序区间[ps 1, ps index - is]从 ps1 起连续取index-is个元素左子树中序区间[is, index - 1]。右子树右子树前序区间[ps index - is 1, pe]左子树区间之后一直到 pe右子树中序区间[index 1, ie]。递归结果分别挂到node.left、node.right最后返回根结点。这里的核心推导一句话即可概括中序中根的位置index决定了左子树规模左子树规模又决定了前序中左右子树的切分点。理解了index - is这个差值整个递归的区间边界就不会记错。05. 优化版本HashMap 缓存中序索引区间递归版在每次递归中都要在中序区间里线性扫描定位根最坏情况下如单支树复杂度退化为 $O(n^2)$。仓库中的姊妹篇 leetcode/05.树/10.重建二叉树1.md 给出了更简洁、更高效的优化版// 缓存中序遍历数组每个值对应的索引 private MapInteger, Integer indexForInOrders new HashMap(); public TreeNode reConstructBinaryTree(int[] pre, int[] in) { for (int i 0; i in.length; i) indexForInOrders.put(in[i], i); return reConstructBinaryTree(pre, 0, pre.length - 1, 0); } private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) { if (preL preR) return null; TreeNode root new TreeNode(pre[preL]); int inIndex indexForInOrders.get(root.val); int leftTreeSize inIndex - inL; root.left reConstructBinaryTree(pre, preL 1, preL leftTreeSize, inL); root.right reConstructBinaryTree(pre, preL leftTreeSize 1, preR, inL leftTreeSize 1); return root; }两个版本的本质区别对比维度区间下标版重建二叉树2HashMap 缓存版重建二叉树1定位根的方式中序区间内线性扫描indexForInOrders.get(root.val)直接取O(1)递归参数4 个区间下标ps/pe/is/ie3 个参数preL/preR/inL利用inR inL leftTreeSize间接表达中序右边界时间复杂度平均 O(n log n)最坏 O(n²)严格 O(n)空间复杂度O(n)递归栈O(n)哈希表 递归栈非法输入处理显式抛异常依赖题目保证输入合法注意 HashMap 版的leftTreeSize inIndex - inL与区间版的index - is是完全一致的推导只是用inL当前中序区间左边界替代了is并省去了显式的中序右边界参数。两个版本放在一起对比学习能同时掌握“区间精确控制”和“哈希表空间换时间”两种典型技巧。06. 复杂度分析与扩展思考6.1 复杂度设二叉树结点数为 n时间每个结点恰好创建一次。区间版每次递归定位根需要扫描中序区间总代价取决于树形平衡树为 O(n log n)单支树退化为 O(n²)HashMap 版每次定位 O(1)整体严格为 O(n)。空间递归深度为树高最坏单支树为 O(n)HashMap 版额外占用 O(n) 的哈希表空间。6.2 边界与考点为什么不能只凭前序后序重建前序后序只能确定根无法唯一划分左右子树边界存在多种合法树因此通常需要“前序中序”或“后序中序”的组合。重复数字会怎样若中序中存在与根同值的多个元素根的位置不唯一重建结果不唯一所以题目明确约束“不含重复的数字”。空树与单结点树空树时外层校验直接返回 null单结点树时左右子树区间均为空递归立即终止两种写法都能正确处理。验证重建结果重建完成后对生成的树做一次中序遍历应与输入的中序序列完全一致再做前序遍历验证前序序列这是最直接的正确性检验方法。遍历实现可参考 leetcode/05.树/02.实现二叉树.md。6.3 与仓库其他树笔记的衔接本仓库的树专题从基础到实战一脉相承可作为系统学习路径leetcode/05.树/00.树的基础介绍.md树的定义、基本术语度、叶子、层次、高度与分类leetcode/05.树/01.二叉树简介.md二叉树的四条核心性质与满/完全/二叉查找树分类leetcode/05.树/02.实现二叉树.md节点定义、前/中/后序遍历、查找、前驱后继、插入删除及深度/广度遍历leetcode/05.树/03.存储二叉树.md链式存储与数组顺序存储两种方式leetcode/05.树/14.从上往下打印二叉树.md借助队列实现层序遍历与重建后的验证打印配合使用面试题库 question/00.面试问题大汇总.md 中还整理了“二叉树深度/广度优先遍历的具体实现”“给定根节点和目标节点找出路径”等高频追问可作为后续练习。07. 小结重建二叉树是一道“理论简单、细节致命”的经典题理论只依赖两条遍历性质细节却在四个区间下标与递归边界的推导上。掌握本文的区间下标版leetcode/05.树/11.重建二叉树2.md与 HashMap 优化版leetcode/05.树/10.重建二叉树1.md并理解二者在复杂度与非法输入处理上的差异面试时无论追问“递归边界怎么推”“重复数字怎么办”“复杂度是多少”都能从容应对。赞分享教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载相关推荐剑指 Offer 07从前序与中序遍历序列重建二叉树分治法详解剑指 Offer 07从前序与中序遍历序列重建二叉树分治法详解 本文基于 LeetCode Book 仓库中《剑指 Offer》章节的题目文档 剑指 Of示例工程AlgoNote 二叉树的还原从遍历序列重建二叉树的三类构造方法与判定原理AlgoNote 二叉树的还原从遍历序列重建二叉树的三类构造方法与判定原理 本文以「算法通关手册」AlgoNote 的「二叉树的还原」章节为主体系统讲解为教程文档知识库CS-Notes 剑指 Offer 题解由前序与中序遍历重建二叉树的递归划分法CS Notes 剑指 Offer 题解由前序与中序遍历重建二叉树的递归划分法 本篇基于 CS Notes 仓库中 剑指 Offer 第 7 题 重建二叉树知识库文档教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考