思路：前序遍历的值做为root , 在中序遍历中找对应的值：
把 中序遍历 划分为 左 | root | 右
对旁边子树，连续递归 左 root 右 | 左 | root | 左 | root | 右
如图：
算法：
算法:
建立哈希表，存入value ， 数组小标做为索引。Map.put(nums[i], i)这样就能找到中序数组的root 位置。递归方法构建旁边子树/
Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preorderIndex = 0;
// 建立hashmap， 存储root 的索引。 这样为了后面定位旁边子树
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return arrayToTree(preorder, 0, preorder.length - 1);
}
private TreeNode arrayToTree(int[] preorder, int left, int right) {
// 递归结束条件，无子树了，返回null
if (left > right) return null;
// root 的值便是pre 数组的值，递增下去
int rootValue = preorder[preorderIndex++];
TreeNode root = new TreeNode(rootValue);
// 分别构建旁边子树
// 左子树确定root 左边的索引， 右子树须要更新 root 右边的索引
root.left = arrayToTree(preorder, left, map.get(rootValue) - 1);
root.right = arrayToTree(preorder, map.get(rootValue) + 1, right);
return root;
}
}
好了这题分享到这，大家加油：P
