剑指 Offer.07-重建二叉树

class Solution {
    // 辅助递归操作执行
    int[] preorder;
    HashMap<Integer,Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        // 将整个中序遍历的数组存储为hash表
        for(int i=0;i<inorder.length;i++){
            dic.put(inorder[i],i);
        }
        return recur(0,0,inorder.length-1);
    }

    TreeNode recur(int root,int left,int right){
        if(left > right) return null;
        // 根据先序遍历 创建根节点
        TreeNode node = new TreeNode(preorder[root]);
        // 获取先序遍历节点在中序遍历数组中的位置
        int i = dic.get(preorder[root]);
        // 划分左右子树
        node.left = recur(root+1,left,i-1); 
        //其中参数中的第一项是在先序遍历中根节点的位置，后面通过中序遍历控制范围
        node.right = recur(root+i-left+1,i+1,right);
        return node;
    }
}