递归构建左右子树。

思路：先根据先序序列的第一个节点建立根节点，然后在中序节点找到这个节点，从而划分出根节点的左、右子树的中序序列。接下来再在先序序列中确定左右子树的先序序列，并由左子树的先序序列与中序序列继续递归建立左右子树。

/**
 * 前序遍历的第一个节点是根节点，在中序遍历中找到这个节点。
 * 中序遍历中这个节点左边的是左子树，右边是右子树。
 * 然后递归去构建左右子树。
 */
public class ReConstructBinaryTree {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root = construct(pre,in,0,pre.length-1,0,in.length-1);
        return  root;
    }

    private TreeNode construct(int[] pre, int[] in, int i, int j, int k, int h) {
        int m = k;
        TreeNode root = new TreeNode(pre[i]);
        while (pre[i] != in[m]) {
            m++;
        }
        if(m == k){
            // 没有左子树时，
            root.left = null;
        } else {
            root.left = construct(pre,in,i+1,i+m-k,k,m-1);
        }
        if(m == h) {
            root.right = null;

        } else {
            root.right = construct(pre,in,i+m-k+1,j,m+1,h);
        }
        return root;

    }
}