本文主要是介绍算法题解记录11+++从前序与中序遍历序列构造二叉树（百日筑基），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 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 <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列
解题准备：
1.了解二叉树：二叉树是递归定义的，当其根节点root！=null时，它有以下性质：root有且仅有两颗子树，分别是左子树left和右子树right。如果把left看成树（left！=null，不过实际也是一棵树），那么其左子树也是一棵二叉树，同理，右子树right也是。
2.了解二叉树前序、中序遍历：二叉树DFS深度优先算法有前序、中序和后序三种，其“序”的概念针对于根节点root。对于前序：root->left->right，也就是根节点、左子树、右子树；对于中序：即左子树、根节点、右子树。
3.猜测可能存在的基础操作：由于需要构造二叉树，而且提供的是两个数组（前序遍历数组、中序遍历数组），所以大概率需要进行“添加”这一基础操作（勉强算是吧）。由于提供只两个数组，感觉可能要遍历。。所以初步认为可能有遍历、添加两个基础操作。
4.模拟操作：
对于下图的二叉树，我们可能轻松得到其前序、中序遍历数组（当然了，这是输入，是已知条件）
那好像看不出什么操作：从定义开始，先寻找一下两个数组的关系。
解题难点1分析：
难点1：如何分步操作，构造这棵二叉树？
从定义出发，我们知道：
1.前序数组是：【根节点，左子树，右子树】
2.中序数组是：【左子树，根节点，右子树】
那么，我们可以通过二者的相互关系，得到左子树前序、中序遍历数组。
可是好像没什么用？拿到左子树的遍历数组（把它当成独立的树），好像又回到原来的问题：怎么分步构造树？
我们知道，在左子树前、中序遍历中，一定也存在根节点，并且在前序遍历中，第一个节点就是根节点。
那，这个性质怎么用？
我们先了解两件事：
1.二叉树由递归构造。
2.对于一棵树，其所有基础操作都要落到具体的节点上，如果拿不到具体节点，什么都是假的。
我们认为题目提供的函数已经具备构造二叉树的能力。
也就是说，既然题目提供了前序、中序数组就能得到二叉树，不如我们借助递归去利用这个函数。
因此，对于树root、left、right，我们把left的前、中序遍历数组，作为函数参数传递。
不过问题来了：传递了第一遍，就没法拿到左子树left的左子树了。而且另一个问题是，前序、中序数组的构造也是个麻烦，每一个节点的左、右子树的长度不一定一样。
也许是缺参数了，如果我们可以提供左、右子树的长度，在进行传递，就可以了？
不行，这一步反而陷入重复论证，因为我们如果可以构造一个左子树（或右子树）数组，那么就一定知道其长度。（left.length）。
不过我们记得：二叉树递归定义，所以其前序、中序遍历也具有递归性，对于左子树的前序遍历序列，有：
left：【根节点left，left的左子树，left的右子树】
把它放进根节点root中，有：【root，【（左子树）left，left左子，left右子】，右子树同理】
也就是说，题目提供的前序、中序遍历数组，其中就包含了某个节点的前、中序遍历。
所以，我们的问题就转换为：如何从题目提供的数组中，拿到某个节点的前、中序遍历。
通过双指针（指向数组）就可以了，既然其具有递归性，那么某个节点的前、中序遍历是连续的（我指的是，数组中的元素连续，比如【1，2，3，4，5】，“1，2，3”连续，“1，3”不连续）
对前序数组，用一个双指针，对中序数组，再用一个双指针，一共4个变量，就可以覆盖数据。
因此，我们的新函数X，需要6个参数，前、中序遍历数组，4个指针。
不过问题又来了：要怎么构造树呢？
我们已经可以针对某个节点，得到其前、中序遍历，那么，就可以一直递归到该节点是叶子节点的时候。
对于某个节点A，A如果是叶子节点，那么它返回其本身即可。
A如果有子树，那么需要把子树连接到其确定位置。
对于函数X，我们认为其具备构造二叉树的能力，只要提供给X一棵树的前、中序遍历，X就可以返回这棵树的根节点。
因此，A有子树，如果是左子树，把左子树的前、中序遍历提供给X，然后A.left=X()即可。
右子树同理。
那么，如何拿到左右子树？
1.前序：根、左、右，第一个一定是根。
2.中序：左、根、右，拿到根，就可确定左、右子树（的长度），然后……
由于数组不存在重复元素，所以不会出错。
如果从前序拿到根，然后在中序中遍历，速度较慢，可以用哈希表。
代码：
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {Map<Integer, Integer> index; // 这里需要注意，如果没写泛型，默认为object，可能出错public TreeNode buildTree(int[] preorder, int[] inorder) {index=new HashMap<Integer, Integer>();int n=inorder.length;for(int i=0; i<n; i++){index.put(inorder[i], i); // 提供一个快速搜索的方式，用数组搜索也一样。}return myBuild(preorder, inorder, 0, n-1, 0, n-1);}// 递归调用private TreeNode myBuild(int[] preorder, int[] inorder, int pre_left,int pre_right, int in_left, int in_right){// 叶子节点，因为叶子节点的前、中序遍历数组为nullif(pre_right<pre_left){return null;}int root_val=preorder[pre_left]; // 得到根节点的值 int in_root=index.get(root_val); // 从中序遍历数组，拿到根节点下标int len=in_root-in_left; // 拿到节点A的遍历数组的长度TreeNode root=new TreeNode(root_val); // 实例化根节点（该根节点并非题解的根节点）root.left=myBuild(preorder, inorder, pre_left+1, pre_left+len,in_left, in_root-1); // 递归调用，前序遍历第一个是根节点，所以加1，加len是因为前、中序遍历长度相同，由于中序先是左子树，所以从left到根节点-1root.right=myBuild(preorder, inorder, pre_left+len+1, pre_right,in_root+1, in_right); // 递归调用，想拿到右子树，那么得从左子树末尾开始，后面都是右子树，所以是pre_right。中序是左根右，所以从根+1到in_rightreturn root;}
}以上内容即我想分享的关于力扣热题11的一些知识。
我是蚊子码农，如有补充，欢迎在评论区留言。个人也是初学者，知识体系可能没有那么完善，希望各位多多指正，谢谢大家。
这篇关于算法题解记录11+++从前序与中序遍历序列构造二叉树（百日筑基）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
