引子：五分钟玩转面试考点-数据结构系列，不会像那种严肃、古板的教科书般的博客文章，而是将晦涩难懂的概念和知识点尽可能幽默的细说出来，或结合生活场景，或从零开始分析。带给大家一个严肃而不失风趣的数据结构。

啦啦啦，啦啦啦~

小胖，今天决定学习一下数据结构——树，于是在网上找了一些资料，网上对于二叉树，讲的最多的也就是树的前序、中序、后序遍历。一般来说，树的遍历，一般使用递归。当然使用栈和队列，也能实现对树的遍历。大家感兴趣可以去，搬运工小胖——浙大网上数据结构公开课。了解下。也可以去名侦探小胖-人之路径，根之输出遍历二叉树

于是我了解怎么遍历二叉树的时候，准备去一展身手，突然发现，我要怎么创造一棵二叉树树？

二叉树是二维结构，若是只是靠一个一维数组，是无法确定一棵树的。所以需要两个数组。而且还是需要前序数组+中序数组或者中序数组+后序数组。

好了，大家带着问题去思考如何建树~~~

下面是一道高频面试题：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解题小贴士：我们基于一个事实：中序遍历一定是 { 左子树中的节点集合 }，root，{ 右子树中的节点集合 }，前序遍历的作用就是找到每棵子树的root位置。前序数组第一个元素就是root元素。

下面咱们就上干货了！！！O(∩_∩)O哈哈~。

1. 我们首先创建树节点

//创建树节点
public class TreeNode {
    int val;  //数据域
    TreeNode left;  //左孩子节点
    TreeNode right;  //右孩子节点
    TreeNode(int x) {
        val = x;
    }
}

2. 分析阶段

我们的原数组：
前序数组pre：{A B C D}
中序数组in：{B C A D}

1. 首先我们在前序数组找到了根节点A。
2. 由此我们可以得知，中序数组中{B C} A {D}，那么B，C节点就是根节点A左边的元素。
   [PS：在pre数组中取长度为2的数组构建新的前序数组。]

3. 于是我们得到了新的数组：
   　前序数组：{Ｂ Ｃ}
   　中序数组：{Ｂ Ｃ}
4. 分析新的前序数组{Ｂ Ｃ}可知，父节点是B。
5. 分析新的中序数组{Ｂ Ｃ}可知，{null} B {C}，那么null就是父节点B的左边的元素。
   [PS：父节点B的左孩子节点是null，我们终止对左子树的遍历]

6.开启对右子树C的分析：
（PS：啥？怎样分析我们？！树中讲究的是"节节平等"，凭啥只对左子树前序数组+中序数组分析，不把我们右子树当节点看？!╭(╯^╰)╮。）
前序数组：{C}
中序数组：{C}
此时根节点是C，那么中序中{null} C {null}。
因为双节点都是null，此时结束循环。

7. 开启对右子树{D}的分析：
   前序数组：{D}
   中序数组：{D}
   此时根节点是D，那么中序中{null} D {null}。
   因为双节点都是null，此时结束循环。

最终结果

image.png

3. 算法编写

上面讲的这么久，感觉有点绕，知道大概的过程就行。对于二叉树的操作，递归怎么能少？？？

结题要诀（递归法）：

O(∩_∩)O哈哈~ 背下来，要考滴...
首先，左右子树的遍历方法是相同的，也就是节节平等。于是我们开始分析如何使用递归的：

1. 递归的出口

根据我们上面分析，若是前序或者中序数组长度为一的情况下，再次递归，那么就要返回null了。

    //1、递归出口
    if (startPre > endPre || startIn > endIn) {
        return null;
    }

2. 递归返回值

每次递归我们的操作是，拼接好孩子节点信息后，返回一个父节点，充当上一个父节点的左或右孩子节点。如此循环，直至根节点。

3. 递归的参数（重点）

我们方法调方法参数如何选择呢？？？
对于前序数组pre，我们采用开始指针startPre+结束指针endPre，来定位处理的数据。
对于中序数组in，我们采用开始指针startIn+结束指针endIn，来定位处理的数据。

我们首先取前序数组的第一个元素pre[startPre]当做父节点，然后我们循环遍历中序数组in，找到in[i]==pre[startPre]。
此时我们已经定位到了_偏移量 (i-startIn)即：新数组长度。：

如何获取左节点？

新的前序数组：
startPre+1---startPre+1+(in-startIn)-1 前序起始位置+1 （现前序数组起始位置） --- （现前序数组起始位置+偏移位置）-1【即：前序数组长度-1】
新的中序数组
startIn --- i-1 中序序列的开始位置 --- 偏移节点 i 的前一个元素

如何获取右节点？

新的前序数组：
startPre+1+(i-startIn)-1+1---endPre 原前序起始位置+偏移量+1（第一个坐标）---原前序数组结束。即：我们是在原前序数组截取的。现前序数组起始位置+偏移量-1是最后一个元素的位置+1是右子树前序的第一个位置。
新的中序数组
i+1 ---endIn 偏移节点 i 的后一个元素---中序数组结束。

只需回想第一次拆分即可~其实本质上有点后序遍历的影子：左右根，访问完了右子树，在输出根节点信息。

4. 代码+注释

package Algorithm;

//创建树节点
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
 class Solution {
    //根据前序+中序 重建二叉树
    //递归思想：递归出口，递归参数，递归返回
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if(pre==null|| in==null){
            return null;
        }
        if(pre.length==0||in.length==0){
            return null;
        }
        return reConstructBinaryTree(pre, in, 0, pre.length - 1, 0, in.length - 1);
    }

    //前序遍历：每次取得第一个元素作为根节点；中序遍历：以前序中第一个元素位置分割，获取节点作用两边的数据
    //中序数组中，找到父节点位置，父节点以左，均是左子树中序数组（1）获取中序遍历数组（2）获取数组长度
    //在截取对应长度的原前序数组（1）获取前序数组
    //以上是一个流程。那么可以确定，一直按这个小流程切分；
    //什么位置为递归出口呢？
    //当数组切分成一个元素时，他就是叶子节点（伪根节点，我们并不知道他是否是叶子节点，还是要继续切分的）。
    // 若继续切分的话，那么便可让其返回null，叶子节点左右两个子树挂null，结束循环。
    //startPre>endPre||startIn>endIn 返回null，结束递归
    //递归的返回值？
    //我们根据上面小流程可知。
    //每次递归都要返回小Root节点，然后从下往上一直拼接，直至根Root节点
    private TreeNode reConstructBinaryTree(int[] pre, int[] in,
                                           int startPre, int endPre, int startIn, int endIn) {
        //1、递归出口
        if (startPre > endPre || startIn > endIn) {
            return null;
        }
        //2、递归返回值,新建返回值，前序数组第一个元素为Root节点的值
        TreeNode root = new TreeNode(pre[startPre]);
        //3、递归表达式
        //按照上述，我们首选要寻找中序数组的，Root元素所在的位置
        for (int i = startIn; i <= endIn; i++) {
            //中序数组已被成功切割，开始计算参数，前序数组和中序数组均要被重新计算
            //startPre已经是Root元素，
            if (pre[startPre] == in[i]) {
                //左子树
                //pre  startPre+1---startPre+1+(in-startIn)-1  起始位置+偏移位置-1【即：数组长度-1】
                //in    startIn ---i-1  左子树其实位置 --- Root节点前一个数据
                root.left=reConstructBinaryTree(pre, in, startPre + 1,
                        startPre + 1 + (i - startIn) - 1,startIn,i-1 );
                //右子树
                //前序数组，startPre+(i-startIn)+1---endPre  即开始位置+偏移量+1（第一个坐标）---endPre
                //中序数组，i+1 ---endIn  Root节点下一个---结束
                //递归代码，我们这个是一维重建二维，
                // 那么我们在确定好递归出口和递归返回值后，我们可以将第一次递归执行情况带入到代码中。
                root.right=reConstructBinaryTree(pre,in,startPre+(i-startIn)+1,endPre,i+1,endIn);
                //找到元素之后，后续就不可能相等了，那么break整个循环。
                break;
            }
        }
        //返回拼接好数据的Root节点，到上一级（可能是左海子节点也可能是右孩子节点）
        return root;
    }
}