JZ4 重建二叉树

前序遍历性质： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。

中序遍历性质： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。

中序遍历 定位root位置 可以计算出左右子树的长度

由前序遍历 左子树的第一个节点就是左孩子 右子树第一个节点就是右孩子，右子树的长度由root长度 + 左子树的长度（由中序遍历的 根节点位置-left ）

其中 root 是根节点在前序遍历中的位置 根节点的位置都是在前序遍历中寻找
left right 是当前子树 在中序遍历中的左右边界。
TreeNode recur(int root, int left, int right)

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;

public class Solution {
    int[] pre; 
    HashMap<Integer, Integer> dic = new HashMap<>();
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        this.pre = pre;
        for(int i = 0; i < vin.length; i++)
            dic.put(vin[i], i);
        return recur(0, 0, vin.length - 1);
    }
    public TreeNode recur(int root, int left, int right){
        if(left>right){return null;}

        TreeNode RootNode = new TreeNode(pre[root]);
        int idx = dic.get(pre[root]);

        RootNode.left = recur(root+1,left,idx-1);
        RootNode.right = recur(root + idx-left +1,idx+1,right);
        return RootNode;
    }
}