输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。
注意:

  • 二叉树中每个节点的值都互不相同；
  • 输入的前序遍历和中序遍历一定合法；

    数据范围

    树中节点数量范围 [0,100][0,100]。

    样例

    给定： 前序遍历是：[3, 9, 20, 15, 7] 中序遍历是：[9, 3, 15, 20, 7] 返回：[3, 9, 20, null, null, 15, 7, null, null, null, null] 返回的二叉树如下所示： 3 / \ 9 20 / \ 15 7
  1. /**
  2.  * Definition for a binary tree node.
  3.  * class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     Map<Integer, Integer> map = new HashMap<>();
  12.     int[] preorder;
  13.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  14.         this.preorder = preorder;
  15.         int n = preorder.length;
  16.         if (n == 0) return null;
  17.         for (int i = 0; i < n; ++i) 
  18.             map.put(inorder[i], i);
  19.         return dfs(0, 0, n - 1);
  20.     }
  22.     TreeNode dfs(int u, int l, int r) {
  23.         if (l > r) return null;
  24.         TreeNode node = new TreeNode(preorder[u]);
  25.         int t = map.get(preorder[u]);
  26.         node.left = dfs(u + 1, l, t - 1);
  27.         node.right = dfs(u + t - l + 1, t + 1, r);
  28.         return node;
  29.     }
  30. }