题干

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

解题思路

这条题目难度就相对于上面几道题就会难上许多，首先我们要先了解如何通过前序和后序遍历手写出二叉树。我们举个例子：

我们复习回顾一下二叉树的遍历方式：

前序遍历：根→左子树→右子树
中序遍历：左子树→根→右子树
后续遍历：左子树→右子树→根

由此我们可以知道前序遍历中第一个数字就是整个树中的根节点，那么在中序遍历中，就可以通过根分为左右两边，如图所示：

从图中我们可以看到根节点把原始的中序变为了左子树的中序和右子树的中序，而在前序当中，也有对应左子树的前序和对应右子树的前序，如图所示：

那么我们又可以根据左子树的前序和中序（前序：2485；中序：8425），以及右子树的前序和中序（前序：367；中序：637）进行进一步划分，以此类推，直到划分完，因此我们仍然可以用递归的方法来解决这个问题，也就是说首先利用前序的第一个节点划分中序的左右子树，根据左右子树的中序节点的个数，来确定前序遍历中对应的左右子树的前序节点的个数，那么我们就把求一整棵树的问题划分求左右子树的问题（可能有些拗口，可以对照着上面的图来理解）。我们来看代码的实现。

代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型一维数组 
     * @param vinOrder int整型一维数组 
     * @return TreeNode类
     */
    public TreeNode function(int[] preOrder,int pre_start,int pre_end, int[] vinOrder,int vin_start, int vin_end){
        if(pre_end<pre_start||vin_end<vin_start){
            return null;
        }
        TreeNode root = new TreeNode(preOrder[pre_start]);
        for(int i = vin_start;i <= vin_end;i++){
            if(preOrder[pre_start] == vinOrder[i]){
                root.left = function(preOrder,pre_start+1,pre_start+i-vin_start,vinOrder,vin_start,i-1);
                root.right = function(preOrder,pre_start+i-vin_start+1,pre_end,vinOrder,i+1,vin_end);
                break;
            }
        }
        return root;
    }

    
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // write code here
        if(preOrder.length==0||vinOrder.length==0||preOrder.length!=vinOrder.length){
            return null;
        }
        return function(preOrder,0,preOrder.length-1,vinOrder,0,vinOrder.length-1);
    }
}