前序遍历

副标题 / 摘要 LeetCode 105 的关键不是死记“前序 + 中序能构树”，而是先看懂两种遍历各自提供什么信息。前序负责告诉你谁是根，中序负责告诉你左右边界，组合起来就能自然落成一个哈希定位的区间分治。 预计阅读时长：12~15 分钟 标签：Hot100、二叉树、分治、哈希表、前序遍历 SEO 关键词：Construct Binary Tree from Preorder and Inorder Traversal, 从前序与中序遍历序列构造二叉树, 前序遍历, 中序遍历, 分治, LeetCode 105 元描述：系统讲透 LeetCode 105 的构树推导、索引分治、哈希优化与多语言实现，并解释为什么一定要先建左子树。 A — Algorithm（题目与算法） 题目还原 给定一棵二叉树的前序遍历 preorder 和中序遍历 inorder，请你重建这棵二叉树并返回它的根节点。 题目保证： 树中元素没有重复 给出的两个数组一定来自同一棵合法二叉树 输入输出 名称 类型 描述 preorder int[] 前序遍历结果 inorder int[] 中序遍历结果 返回值 TreeNode 重建后的二叉树根节点 示例 1 输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出：[3,9,20,null,null,15,7] 示例 2 输入：preorder = [-1], inorder = [-1] 输出：[-1] 提示 1 <= preorder.length <= 3000 inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder 和 inorder 都没有重复元素 inorder 中的每个值都出现在 preorder 中 preorder 保证是某棵树的前序遍历 inorder 保证是同一棵树的中序遍历 目标读者 一看到“根据遍历结果构树”就会混淆前序和中序职责的学习者 想把“树的遍历顺序”和“树的结构恢复”建立稳定联系的开发者 做过 94、114 之后，想继续巩固树结构题的读者 背景 / 动机 这题最值得学的地方是： ...