CS-Notes 剑指 Offer 题解：由前序与中序遍历重建二叉树的递归划分法

CS-Notes 剑指 Offer 题解由前序与中序遍历重建二叉树的递归划分法【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本篇基于 CS-Notes 仓库中 剑指 Offer 第 7 题 - 重建二叉树 展开完整讲解根据前序遍历与中序遍历序列还原整棵二叉树这一经典面试题的题面约束、递归划分思路、O(n) 时间复杂度的 Java 实现并逐步推演递归参数preL / preR / inL的边界推导过程。读完本篇后你可以独立写出可复制运行的重建代码理解为什么用 HashMap 缓存中序索引能把总复杂度降到 O(n)并掌握空树、退化链等边界情况下的行为同时了解该思想在仓库其他树类题目中的延伸应用。一、题目描述与输入约束题目要求根据二叉树的前序遍历和中序遍历的结果重建出该二叉树。关键约束只有一条但至关重要输入的前序遍历和中序遍历的结果中都不含重复的数字。这一约束是算法能够唯一确定树结构的前提——如果节点值可以重复前序中第一个值在中序里可能出现多次根节点在中序中的位置就无法唯一确定划分也就无从谈起。从题目约束还可以推断出隐含前提两个数组长度相同、由同一棵树遍历而来因此无需在解法中做一致性校验可以直接按合法输入处理。二、核心思路一个位置 一次划分 两次递归重建二叉树的可行源于两种遍历顺序各自的结构性信息前序遍历的第一个值一定是当前子树的根节点。因为前序的访问顺序是根 - 左子树 - 右子树DFS 中先visit(root)再递归左、右可参考 Leetcode 题解 - 树 中对前、中、后序三种 DFS 顺序的定义中序遍历中根节点把序列恰好切成左右两半。中序的顺序是左子树 - 根 - 右子树所以根的值在中序序列左侧的部分就是左子树的全部节点右侧的部分就是右子树的全部节点。由此得到一个可以不断自我收缩的子问题在当前子树对应的前序区间中取第一个元素作为根用它在中序区间里的下标inIndex算出左子树节点个数leftTreeSize inIndex - inL然后前序区间同步地切成左子树前序和右子树前序两段对左右子树各自递归求解。直到区间为空preL preR时返回null递归自然终止。举例推演沿用 Leetcode 题解 - 树 中前中后序遍历一节给出的示例树1 / \ 2 3 / \ \ 4 5 6它的前序遍历为[1 2 4 5 3 6]中序遍历为[4 2 5 1 3 6]。按上述思路手动执行重建过程步骤当前子树的前序区间根根在中序中的下标左子树规模说明1[1 2 4 5 3 6]133中序[4 2 5 \| 1 \| 3 6]左侧 3 个节点归左子树2[2 4 5]21相对左子树区间1左子树前序取[4 5]去掉根即[4 5]右子树为[5]3[3 6]3003 无左子树右子树前序为[6]4~6单节点 4、5、6———leftTreeSize为 0递归到preL preR返回null可以看到每一步递归都把问题规模严格变小且前序区间长度 对应中序区间长度这一不变式在收缩过程中始终成立。三、完整 Java 实现含参数边界推导下面是原文档给出的可运行解法这里补充了每段代码的作用说明// 缓存中序遍历数组每个值对应的索引 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; }代码中的TreeNode为面试平台的标准二叉树节点类含val与left、right字段。3.1 为什么要先建 HashMap朴素做法是每确定一个根就在中序数组里线性indexOf它的下标最坏情况树退化成一条链下总代价为 O(n²)。解法在入口处遍历一次中序数组把值 - 下标存入indexForInOrders此后每次定位根在中序中的位置都是 O(1)。由于节点值不重复HashMap的 key 不会冲突。3.2 递归参数边界是怎么推出来的递归函数签名reConstructBinaryTree(pre, preL, preR, inL)的四个参数含义是preL ~ preR当前子树在前序数组中对应的闭区间inL当前子树在中序数组中的起始下标中序区间的右端点不需要显式传入它等于inL (preR - preL)由区间长度相等这一不变式唯一确定。设当前根为pre[preL]它在中序中的下标为inIndex则左子树规模leftTreeSize inIndex - inL即中序区间里根左侧的元素个数左子树前序区间紧跟在根之后的leftTreeSize个元素即[preL 1, preL leftTreeSize]对应中序区间仍从inL开始右子树前序区间[preL leftTreeSize 1, preR]对应中序区间从inL leftTreeSize 1开始跳过左子树和根。入口调用reConstructBinaryTree(pre, 0, pre.length - 1, 0)表示整棵树的前序区间就是整个数组、中序区间从下标 0 开始。3.3 复杂度时间 O(n)每个节点恰好被处理一次建一次根且建根后通过 HashMap 定位中序下标是 O(1)共 n 个节点总计 O(n)空间 O(n)HashMap 存 n 个映射另外递归栈深度取决于树的形态——平衡树为 O(log n)最坏退化为链状时为 O(n)。四、边界情况与常见追问空输入若pre为空数组入口调用变为reConstructBinaryTree(pre, 0, -1, 0)preL preR直接命中返回null整个方法安全地返回null无需额外判空单边子树当inIndex inL时leftTreeSize为 0左子树递归调用参数为preL 1 preL立即返回null等价于没有左子树右子树同理。单边子树不需要特殊分支重复值题目已排除重复数字。若面试中被追问有重复值怎么办可以回答HashMap 中同一值会对应多个下标需要对候选位置逐一尝试并配合剪枝/校验唯一性不再保证输入合法性校验本题假设输入合法。若在开放编码场景中可补充两项校验两数组长度相等且两数组包含的元素集合一致对同一序列排序后逐项比较或用计数器比对不满足则返回null能否只用前序 后序重建不能仅满二叉树例外。前序确定根、后序确定叶子的相对关系但无法唯一判定某个节点是左子树的最后一个节点还是右子树的第一个节点划分信息缺失因此会出现多棵结构不同的树对应同一对序列的情况。而前序 中序之所以可行正是因为中序提供了左右分界这一关键信息。五、在仓库中的延伸阅读先定位根、再切左右、递归求解是这一批树题目的公共骨架仓库中同系列的几道题可以对照着看二叉搜索树的后序遍历序列判断一个数组是否为 BST 后序序列同样采用取区间末尾为根按值大小划分左右子树区间后递归验证的结构只是划分依据从查下标换成了利用 BST 的大小关系扫描切分点序列化二叉树用带空节点占位符#的前序风格字符串编码树再解码本质上也是前序位置 递归收缩的变体可以作为另一种保存/还原树结构的方案与本题对照剑指 Offer 题解 - 目录本题在整个题解体系中的位置可顺带浏览第 26~37 题这一片树章节树的子结构、镜像、层次打印、序列化等Leetcode 题解 - 树其中前中后序遍历一节给出了三种 DFS 遍历的伪代码和非递归实现是理解为什么前序首元素是根、中序能划分左右的直接依据。六、小结重建二叉树的解法可以浓缩成三句话前序首元素定根中序下标定界左右区间同步收缩递归。实现上的两个要点是把查根在中序中的位置用 HashMap 提到 O(1)以及严格维护前序区间长度 中序区间长度这一不变式来推导preL/preR/inL的递推公式。掌握这套递归划分的写法后第 33 题的 BST 后序验证、第 37 题的序列化反序列化等同类题目都可以在同一框架下快速迁移。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考