输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 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
/**
* @Title: buildTree
* @Description: 递归
* @author: itbird
* @date 2022年3月15日 下午3:59:16
* @param preorder
* @param inorder
* @return TreeNode 时间复杂度: O(N) 空间复杂度: O(N)
*/
int[] preorder; // 保存的前序遍历数据，用于过程中查找根节点
HashMap<Integer, Integer> map = new HashMap<>(); // 保存中序遍历结果，key为节点值，value为位置
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
// 将中序遍历的值及索引放在map中，方便递归时获取左子树与右子树的数量及其根的索引
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
// 三个索引分别为
// 当前根的的索引
// 递归树的左边界，即数组左边界
// 递归树的右边界，即数组右边界
return buildMyTree(0, 0, inorder.length - 1);
}
private TreeNode buildMyTree(int root, int left, int right) {
if (left > right) {
// 相等的话就是自己
return null;
}
// 构建根节点
TreeNode node = new TreeNode(preorder[root]);
// 获取在中序遍历中根节点所在索引，以方便获取左子树的数量
int idx = map.get(preorder[root]);
// 左子树的根的索引为先序中的根节点+1
// 递归左子树的左边界为原来的中序in_left
// 递归左子树的右边界为中序中的根节点索引-1
node.left = buildMyTree(root + 1, left, idx - 1);
// 右子树的根的索引为先序中的 当前根位置 + 左子树的数量 + 1
// 递归右子树的左边界为中序中当前根节点+1
// 递归右子树的右边界为中序中原来右子树的边界
node.right = buildMyTree(root + idx - left + 1, idx + 1, right);
return node;
}
