import java.util.HashMap;

/**

* 105 重建二叉树

*/

public class BuildTree {

public TreeNode buildTree(int[] preorder, int[] inorder) {

if(preorder.length!=inorder.length || preorder.length==0){

return null;

}

HashMap<Integer, Integer> map = new HashMap<>();

for(int i=0; i<inorder.length; i++){

map.put(inorder[i], i);

}

TreeNode root = dp(0, 0, inorder.length-1, preorder, map);

return root;

}

TreeNode dp(int pos, int left, int right, int[] preorder, HashMap<Integer, Integer> map){

// 递归终止

if(left>right){

return null;

}

// 建立根节点

TreeNode node = new TreeNode(preorder[pos]);

// 划分根节点、左子树、右子树

int i = map.get(preorder[pos]);

// 开启左子树递归

node.left = dp(pos+1, left, i-1, preorder, map);

// 开启右子树递归

node.right = dp(pos+i-left+1, i+1, right, preorder, map);

return node;

}

}