1. 题目
描述
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点，系统会自动输出整颗树做答案对比
数据范围：n ≤2000，节点的值 -10000≤val≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)
示例1
输入：
[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
返回值：
{1,2,3,4,#,5,6,#,7,#,#,8}
说明：
返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示
示例2
输入：
[1],[1]
返回值：
{1}
示例3
输入：
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值：
{1,2,5,3,4,6,7}
2. 解题思路
本题需要通过二叉树的前序遍历结果与中序遍历结果构建出二叉树来，因此需要先了解二叉树前序遍历与中序遍历的规律：
1）前序遍历，根节点是在最前面；
2）中序遍历，根节点是在中间位置（即：根节点元素前面的为左子树，后面的为右子树）。
了解了规律，再来看思路：
根据思路，对应的递推公式如下：
有了递推公式，就可以很方便的写出代码。
如果文字描述的不太清楚，你可以参考视频的详细讲解。
Python版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1372249Golang版本：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1364782
3. 编码实现
核心代码如下：
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param preOrder int整型一维数组
* @param vinOrder int整型一维数组
* @return TreeNode类
*/
func reConstructBinaryTree(pre []int, vin []int) *TreeNode {
// write code here
// 2. 递归终止条件（pre、vin长度一样，只需要判断一个即可）
if len(pre) == 0 {
return nil
}
// 1. 问题分解（递推公式）
// 1.1 根节点（前序遍历的第一个值）
root := &TreeNode{Val: pre[0]}
// 1.2 根节点在中序遍历中的位置
index := getIndex(vin, pre[0])
// 1.3 以根节点索引为分割线，将数组pre、vin分为左右两部分
root.Left = reConstructBinaryTree(pre[1:index+1], vin[:index]) //左部分构成左子树（切片截取：左闭右开）
root.Right = reConstructBinaryTree(pre[index+1:], vin[index+1:]) //右部分构成右子树
return root
}
func getIndex(vin []int, v int) int {
for index, data := range vin {
if data == v {
return index //根据题目：pre 和 vin 均无重复元素，因此找到元素即可返回
}
}
return 0
}具体完整代码你可以参考下面视频的详细讲解。
4.小结
根据二叉树的前序遍历结果与中序遍历结果构建二叉树可以通过以下方法完成：
创建根节点（跟节点的值为前序遍历的第一个数）；
查找根节点在中序遍历中的位置；
以根节点索引为分割线，将前序遍历数组pre、中序遍历数组vin分为左右两部分；左部分构成根节点的左子树，右部分构成根节点的右子树。
《数据结构与算法》深度精讲课程正式上线啦！七大核心算法模块全解析：
✅ 链表
✅ 二叉树
✅ 二分查找、排序
✅ 堆、栈、队列
✅ 回溯算法
✅ 哈希算法
✅ 动态规划
无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！
Python编码实现：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ss897667807Java编码实现：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ss161443488Golang编码实现：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ss63997
对于二叉树的相关算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。
今日佳句：日出江花红胜火，春来江水绿如蓝。