输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
限制：
0 <= 节点个数 <= 5000
题解1：分治法（递归思想）
思路：
前序遍历的第 1 个结点一定是二叉树的根结点；
在中序遍历中，根结点把中序遍历序列分成了两个部分，左边部分构成了二叉树的根结点的左子树，右边部分构成了二叉树的根结点的右子树。
查找根结点在中序遍历序列中的位置，可以遍历，也可以在一开始就记录下来。
1 import java.util.HashMap;
2 import java.util.Map;
3
4 class TreeNode {
5 int val;
6 TreeNode left;
7 TreeNode right;
8
9 TreeNode(int x) {
10 val = x;
11 }
12 }
13
14
15 public class Solution {
16
17 // 使用全局变量是为了让递归方法少传一些参数，不一定非要这么做
18
19 private Map<Integer, Integer> reverses;
20 private int[] preorder;
21
22 public TreeNode buildTree(int[] preorder, int[] inorder) {
23 int preLen = preorder.length;
24 int inLen = inorder.length;
25
26 // 可以不做判断，因为题目中给出的数据都是有效的
27 if (preLen != inLen) {
28 return null;
29 }
30
31 this.preorder = preorder;
32
33 // 以空间换时间，否则，找根结点在中序遍历中的位置需要遍历
34 reverses = new HashMap<>(inLen);
35 for (int i = 0; i < inLen; i++) {
36 reverses.put(inorder[i], i);
37 }
38
39 return buildTree(0, preLen - 1, 0, inLen - 1);
40 }
41
42 /**
43 * 根据前序遍历数组的 [preL, preR] 和 中序遍历数组的 [inL, inR] 重新组建二叉树
44 *
45 * @param preL 前序遍历数组的区间左端点
46 * @param preR 前序遍历数组的区间右端点
47 * @param inL 中序遍历数组的区间左端点
48 * @param inR 中序遍历数组的区间右端点
49 * @return 构建的新二叉树的根结点
50 */
51 private TreeNode buildTree(int preL, int preR,
52 int inL, int inR) {
53 if (preL > preR || inL > inR) {
54 return null;
55 }
56 // 构建的新二叉树的根结点一定是前序遍历数组的第 1 个元素
57 int pivot = preorder[preL];
58 TreeNode root = new TreeNode(pivot);
59
60 int pivotIndex = reverses.get(pivot);
61
62 // 这一步得画草稿，计算边界的取值，必要时需要解方程，并不难
63 root.left = buildTree(preL + 1, preL + (pivotIndex - inL), inL, pivotIndex - 1);
64 root.right = buildTree(preL + (pivotIndex - inL) + 1, preR, pivotIndex + 1, inR);
65 return root;
66 }
67 }
题解2：
递归解析：
递推参数： 前序遍历中根节点的索引pre_root、中序遍历左边界in_left、中序遍历右边界in_right。
终止条件： 当 in_left > in_right ，子树中序遍历为空，说明已经越过叶子节点，此时返回 nullnull 。
递推工作：
1.建立根节点root： 值为前序遍历中索引为pre_root的节点值。
2.搜索根节点root在中序遍历的索引i： 为了提升搜索效率，本题解使用哈希表 dic 预存储中序遍历的值与索引的映射关系，每次搜索的时间复杂度为 O(1)O(1)。
3.构建根节点root的左子树和右子树： 通过调用 recur() 方法开启下一层递归。
左子树： 根节点索引为 pre_root + 1 ，中序遍历的左右边界分别为 in_left 和 i - 1。
右子树： 根节点索引为 i - in_left + pre_root + 1（即：根节点索引 + 左子树长度 + 1），中序遍历的左右边界分别为 i + 1 和 in_right。
4.返回值： 返回 root，含义是当前递归层级建立的根节点 root 为上一递归层级的根节点的左或右子节点。
1 class Solution {
2 HashMap<Integer, Integer> dic = new HashMap<>();
3 int[] po;
4 public TreeNode buildTree(int[] preorder, int[] inorder) {
5 po = preorder;
6 for(int i = 0; i < inorder.length; i++)
7 dic.put(inorder[i], i);
8 return recur(0, 0, inorder.length - 1);
9 }
10 TreeNode recur(int pre_root, int in_left, int in_right) {
11 if(in_left > in_right) return null;
12 TreeNode root = new TreeNode(po[pre_root]);
13 int i = dic.get(po[pre_root]);
14 root.left = recur(pre_root + 1, in_left, i - 1);
15 root.right = recur(pre_root + i - in_left + 1, i + 1, in_right);
16 return root;
17 }
18 }
题解3：
1 class Solution {
2 public TreeNode buildTree(int[] preorder, int[] inorder) {
3 return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
4 }
5
6 /**
7 * preStart - preEnd 代表了在 preorder[] 中查找的区间范围
8 * inStart - inEnd 代表了在 inorder[] 中查找的区间范围
9 */
10 private TreeNode buildTree(int[] preorder, int preStart, int preEnd
11 , int[] inorder, int inStart, int inEnd) {
12 // 显而易见的结束条件
13 if (preStart > preEnd || inStart > inEnd) {
14 return null;
15 }
16 // 前序遍历的第一个节点为 root
17 TreeNode root = new TreeNode(preorder[preStart]);
18
19 // 在中序遍历的查找区间中找到 root 所处位置
20 for (int i = inStart; i <= inEnd; i++) {
21
22 if (inorder[i] == preorder[preStart]) {
23 // 前序区间的 start 从根节点后一位开始
24 // 前序区间的 end 是中序遍历确定的左子树节点个数 + 原先的preStart
25 // 中序区间的 start 不变，因为从头开始找左子树
26 // 中序区间的 end 最多达到当前根节点的前一位
27 root.left = buildTree(preorder, preStart + 1, i - inStart + preStart
28 , inorder, inStart, i - 1);
29
30 // 前序区间的 start 从当前根节点跳过左子树个数开始
31 // 前序区间的 end 保持不变，扫描到底
32 // 中序区间的 start 从根节点的后一位开始
33 // 中序区间的 end 保持不变
34 root.right = buildTree(preorder, i - inStart + preStart + 1, preEnd
35 , inorder, i + 1, inEnd);
36 }
37 }
38 return root;
39 }
40 }
题解4：
使用Arrays.copyOfRange（）方法
1 class Solution {
2 public TreeNode buildTree(int[] preorder, int[] inorder) {
3 int n = preorder.length;
4 if (n == 0)
5 return null;
6 int rootVal = preorder[0], rootIndex = 0;
7 for (int i = 0; i < n; i++) {
8 if (inorder[i] == rootVal) {
9 rootIndex = i;
10 break;
11 }
12 }
13 TreeNode root = new TreeNode(rootVal);
14
15 root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + rootIndex),Arrays.copyOfRange(inorder, 0, rootIndex));
16
17 root.right = buildTree(Arrays.copyOfRange(preorder, 1 + rootIndex, n),Arrays.copyOfRange(inorder, rootIndex + 1, n));
18
19 return root;
20 }
21 }
来源：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/