输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
class Solution {
Map inorderMap = new HashMap<>();
int[] preorder;
public TreeNode recur(int root, int inorderLeft, int inorderRight) {
// 使用中序遍历的左右指针判断这个根节点下有没有元素
if (inorderLeft > inorderRight) return null;
TreeNode rootNode = new TreeNode(this.preorder[root]);
// 获取根节点在中序遍历中的位置 用于计算左子树 和 右子树的长度 用于判断这个根节点下有没有元素
int inorderIdx = inorderMap.get(this.preorder[root]);
// 通过长度可以计算中左右子树根节点在前序遍历中的位置
rootNode.left = recur(root + 1, inorderLeft, inorderIdx - 1);
// 计算左子树的长度
int leftTreeLength = inorderIdx - inorderLeft;
rootNode.right = recur(root + leftTreeLength + 1, inorderIdx + 1, inorderRight);
return rootNode;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
// 使用Map记录每个元素在中序遍历的位置
for (int i = 0; i < inorder.length; ++i) this.inorderMap.put(inorder[i], i);
return recur(0, 0, inorder.length - 1);
}
}
