根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
1 class Solution {
2 HashMap<Integer,Integer> map;
3 public TreeNode buildTree(int[] preorder, int[] inorder) {
4 //先使用哈希表建立中序遍历的下标与节点的映射
5 map = new HashMap<>();
6 for(int i = 0;i<inorder.length;i++)
7 map.put(inorder[i], i);
8 return process(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
9 }
10 public TreeNode process(int[] preorder,int[] inorder,int preLeft,int preRight,int inLeft,int inRight)
11 {
12 if(preLeft>preRight)
13 return null;
14 int preRoot = preLeft;
15 int inRoot = map.get(preorder[preLeft]);
16 TreeNode node = new TreeNode(preorder[preRoot]);
17 int sizeLeft = inRoot-inLeft;
18 node.left = process(preorder,inorder,preLeft+1,preLeft+sizeLeft,inLeft,inRoot-1);
19 node.right = process(preorder,inorder,preLeft+sizeLeft+1,preRight,inRoot+1,inRight);
20 return node;
21 }
22 }
21.03.15 LeetCode105. 从前序与中序遍历序列构造二叉树
原文：https://www.cnblogs.com/pionice/p/14535546.html