输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

    假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

    示例 1:
    image.png

    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

    1. class Solution {
    2.     /**
    3.     map存放中序遍历对应的下标,然后根据前序遍历创建根节点,再递归创建左节点和右节点
    4.      */
    5.     int[] preorder;
    6.     Map<Integer, Integer> map = new HashMap<>();
    7.     public TreeNode buildTree(int[] preorder, int[] inorder) {
    8.         this.preorder = preorder;
    9.         int n = preorder.length;
    10.         for (int i = 0; i < n; ++i) map.put(inorder[i], i);
    11.         return recur(0, 0, n - 1);
    12.     }
    13.     private TreeNode recur(int root, int left, int right) {
    14.         if (left > right) return null;
    15.         TreeNode node = new TreeNode(preorder[root]);
    16.         int u = map.get(preorder[root]);  //u是根节点对应的中序遍历下标
    17.         //left为前序遍历 根节点下一个树,左右区间为中序遍历根节点对应下标前面
    18.         node.left = recur(root + 1, left, u - 1);
    19.         //u - left + 1为左子树的长度
    20.         node.right = recur(root + u - left + 1, u + 1, right);
    21.         return node;
    22.     }
    23. }