思路：前序遍历的值做为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
