手把手教你如何重建二叉树（超精彩配图）
一、二叉树的重建
在LeetCode中有这么一道算法题：《重建二叉树》
（一）面试题07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：
3
/ \
9 20
/ \
15 7限制：
0 <= 节点个数 <= 5000
（二）分析该题目
从题目中可以看到，给出了两个数组，一个书前序遍历二叉树得出的结果，一个是中序遍历二叉树得出的结果。
利用这两个结果，来还原出一颗二叉树。
首先你要知道什么是前序遍历和中序遍历。你还要知道，给你一颗二叉树，使用这些遍历的算法怎么得到遍历的结果，不然是没办法继续完成重建二叉树的。
如果你还不输入二叉树的遍历，可以看这篇文章：
《我是怎么一步一步调试出来二叉树的遍历(超精彩配图)，二叉树遍历再也不用愁了》
先来看一下前序遍历
如下图所示，前序遍历就是：
根—左—右
再来看一下中序遍历：
终须遍历则是：
左—根—右
最终就得到的这样的数组：
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]如果你够细心的话，会发现前序遍历的第一个是3，而这个3就是整颗二叉树的根节点;
在看一下中序的结果：
如下图所示，如果我们把中序中3所在的位置的左右两部分分割开，就得到了根节点3的所有左边和右边的节点。
[9],[3],[15,20,7]
不难发现，如果我们以此类推的话，就可以还原出一颗二叉树。
（三）java代码实现
package tree;
import java.util.Arrays;
/**
* @Auther: truedei
* @Date: 2020 /20-6-9 12:00
* @Description: 二叉树重建
*/
public class Solution {
/**
* 根据前序和中序遍历的二叉树的结果构建二叉树
* @param preorder 前序遍历结果的数组
* @param inorder 中序遍历结果的数组
* @return 返回一个构建好的二叉树
*/
static public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null || preorder.length==0)
return null;
//1，获取树的根节点的value值
TreeNode root = new TreeNode(preorder[0]);
//2，查找每一次根节点在中序遍历结果中的位置
int index = findIndex(preorder[0],inorder);
//3,构建left左子树
// root.left = buildTree(左子树前序数组，左子树中序数组)
root.left = buildTree(Arrays.copyOfRange(preorder,1,index + 1 ),
Arrays.copyOfRange(inorder,0,index));
//4，构建reght右子树
// root.right=buildTree(右子树前序数组，右子树中序数组)
root.right = buildTree(Arrays.copyOfRange(preorder,index+1,preorder.length),
Arrays.copyOfRange(inorder,index+1,inorder.length));
return root;
}
/**
* 查找根的index（在中序中的位置）的函数
* @param preorderData 节点
* @param inorder 每一次的中序数组
* @return 索引位置
*/
static public int findIndex(int preorderData, int[] inorder){
for (int i = 0; i < inorder.length; i++) {
if(inorder[i]==preorderData)
return i;
}
return 0;
}
public static void main(String[] args) {
TreeNode treeNode = buildTree(new int[]{3,9,20,15,7}, new int[]{9,3,15,20,7});
theFirstTraversal(treeNode);
}
//先序遍历 用于测试最终的结果是否正确
public static void theFirstTraversal(TreeNode root) {
System.out.println(root.val);
if (root.left != null) { //使用递归进行遍历左孩子
theFirstTraversal(root.left);
}
if (root.right != null) { //递归遍历右孩子
theFirstTraversal(root.right);
}
}
}核心代码：
用于递归构建二叉树
/**
* 根据前序和中序遍历的二叉树的结果构建二叉树
* @param preorder 前序遍历结果的数组
* @param inorder 中序遍历结果的数组
* @return 返回一个构建好的二叉树
*/
static public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null || preorder.length==0)
return null;
//1，获取树的根节点的value值
TreeNode root = new TreeNode(preorder[0]);
//2，查找每一次根节点在中序遍历结果中的位置
int index = findIndex(preorder[0],inorder);
//3,构建left左子树
// root.left = buildTree(左子树前序数组，左子树中序数组)
root.left = buildTree(Arrays.copyOfRange(preorder,1,index + 1 ),
Arrays.copyOfRange(inorder,0,index));
//4，构建reght右子树
// root.right=buildTree(右子树前序数组，右子树中序数组)
root.right = buildTree(Arrays.copyOfRange(preorder,index+1,preorder.length),
Arrays.copyOfRange(inorder,index+1,inorder.length));
return root;
}
/**
* 查找根的index（在中序中的位置）的函数
* @param preorderData 节点
* @param inorder 每一次的中序数组
* @return 索引位置
*/
static public int findIndex(int preorderData, int[] inorder){
for (int i = 0; i < inorder.length; i++) {
if(inorder[i]==preorderData)
return i;
}
return 0;
}一定有十万个为什么，为什么要这样写，其实写法有很多。接下来咱们一起来调试一下，看看执行时是什么样子的。
（四）IDEA调试代码，详细查看构建的过程
我这里使用的工具是IDEA。
为了方便调试，便于查看每一次执行的结果，我们先打上断点。
然后Debug运行此java文件，如下图所示，就是最初运行的结果
进一步了解一下：
可以看到现在传入的前序数组和中序数组分别为： 前序遍历 preorder = 3,9,20,15,7 中序遍历 inorder = 9,3,15,20,7
一定要有印象哦
下图就是看到的我们接着上一个图下一步之后的结果。
在这个操作了，我们起作用的是
TreeNode root = new TreeNode(preorder[0]);我们拿到了前序数组0号位置的数据，至于为什么一定要拿到前序数组中的0号位置的数据，可以看一下下面的图。解释的很清楚了。
下一步之后，就会看到下面的结果;
这里我们要去查找拿到的3在中序数组中的所在的位置 至于为什么，请看下图
这里就不在说明Arrays.copyOfRange()的作用了，请看（五）附Arrays.copyOfRange()的用法，给大家准备好了。
接下来就要使用拿到的index，去构建一个左节点了
继续下一步
继续下一步
继续下一步
开始构造3右边所有的节点：
这样我们就拿到了20的左节点
现在就可以构造出最后一个节点了，不过因为是顺序执行的，所以省略n步
验证是否正确：
到此为止，结束了。
经过Debug一遍，心里一定很清晰了。
（五）附Arrays.copyOfRange()的用法
与使用System.arraycopy进行数组复制类似的， Arrays提供了一个copyOfRange方法进行数组复制。
Arrays.copyOfRange()的格式如下：
第一个参数表示源数组第二个参数表示开始位置(取得到)第三个参数表示结束位置(取不到)
copyOfRange(int[] original, int from, int to)实例代码：
import java.util.Arrays;
public class HelloWorld {
public static void main(String[] args) {
int a[] = new int[] { 18, 62, 68, 82, 65, 9 };
// 不同的是System.arraycopy，需要事先准备好目标数组，并分配长度。
// copyOfRange只需要源数组就就可以了，通过返回值，就能够得到目标数组了。
// 除此之外，需要注意的是 copyOfRange 的第3个参数，表示源数组的结束位置，是取不到的。
// copyOfRange(int[] original, int from, int to)
// 第一个参数表示源数组
// 第二个参数表示开始位置(取得到)
// 第三个参数表示结束位置(取不到)
int[] b = Arrays.copyOfRange(a, 0, 3);
for (int i = 0; i < b.length; i++) {
System.out.print(b[i] + "\t");//18 62 68
}
// 溢位复制
System.out.println();
int[] C = Arrays.copyOfRange(a, 0, 7);
for (int i = 0; i <C.length; i++) {
System.out.print(C[i] + "\t");//18 62 68 82 65 9 0
}
}
}这里参考地址：