剑指OfferJZ4：重建二叉树-java版

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

前序遍历：中左右 ——>（特点：靠前的一定是子树的父节点，即“中”）利用前序序列来定位“中” 中序遍历：左中右 ——>在得到“中”的基础上，利用中序序列来定位“左”“右”

首先，利用前序序列定位到“中”（根节点）为1，再根据1到中序序列定位节点1的左右子树，如图：左子树包含4 7 2 ；右子树包含5 3 8 6

接着，利用前序序列定位到“中”为2，再根据2到中序序列定位节点2的左右子树，如图：左子树包含：4 7；右子树为空

接着，利用前序序列定位到“中”为4，再根据4到中序序列定位节点4的左右子树，如图：左子树为空；右子树为7

看，根节点1的左子树全部搞定！所以就不用再操作这步：“利用前序序列定位到“中”为7”了

接着，利用前序序列定位到“中”为3，再根据3到中序序列定位节点3的左右子树，如图：左子树为5；右子树包含：8 6 接着，利用前序序列定位到“中”为5，再根据5到中序序列定位节点5的左右子树，如图：左子树为空；右子树为空，不用画了

接着，利用前序序列定位到“中”为6，再根据6到中序序列定位节点6的左右子树，如图：左子树为8；右子树为空

右子树也全部搞定！ 这样我们就根据二叉树的前序遍历和中序遍历重建出了该二叉树！

那么我们根据后序遍历的规则——左右中 便可得出后序序列为 7 4 2 5 8 6 3 1

 class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode next;

    TreeNode (int x){
        val=x;
    }
}

public class jz4 {
    private static int index=0;
    private static TreeNode solve(int[] pre,int[] tempIn){//pre前序序列 tempIn中序序列
        int len1=0;//当前节点的左子树节点个数
        int len2=0;//当前节点的右子树节点个数
        for(int i=0;i