输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] 示例 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
限制：
0 <= 节点个数 <= 5000
int[] preorder;
HashMap<Integer, Integer> map = new HashMap<>();
// 前序遍历 preorder: 根 -- 左 -- 右 第一个肯定是根节点
// 中序遍历 inorder: 左 -- 根 -- 右
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}
return rebuild(0, 0, inorder.length - 1);
}
// pre_root_index : 根节点 在 前序遍历中的下标
// in_left_index: 该节点在中序遍历中的左边界
// in_right_index: 该节点在中序遍历中的右边界
public TreeNode rebuild(int pre_root_index, int in_left_index, int in_right_index){
if(in_left_index > in_right_index) return null;
// 根节点在中序遍历中的位置：in_root_index
int in_root_index = map.get(preorder[pre_root_index]);
// 创建一个根节点
TreeNode node = new TreeNode(preorder[pre_root_index]);
// 寻找node的左节点:
// 在前序遍历中的位置就是 根节点的下标 + 1（右边一个单位）
// 在中序遍历中的位置就是： 1. 左边界不变，2. 右边界就是根节点的左边一个单位 in_root_index - 1
node.left = rebuild(pre_root_index + 1, in_left_index, in_root_index - 1);
// 寻找node的右节点:
// 在前序遍历中的位置就是 根节点的下标 + 左子树长度 + 1
// 在中序遍历中的位置就是： 1. 左边界在根节点的右边一个单位 in_root_index + 1, 2. 右边界不变
node.right = rebuild(pre_root_index + in_root_index - in_left_index + 1, in_root_index + 1, in_right_index);
return node;
}
}