根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder =[3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
代码：
/**
*Definitionforabinarytreenode.
*publicclassTreeNode{
*intval;
*TreeNodeleft;
*TreeNoderight;
*TreeNode(intx){val=x;}
*}
*/
classSolution{
intpreorder[];
intinorder[];
intcount=0;
HashMap<Integer,Integer>map=newHashMap<Integer,Integer>();
publicTreeNodebuildTree(int[]preorder,int[]inorder){
this.preorder=preorder;
this.inorder=inorder;
inti=0;
for(intx:inorder){
map.put(x,i++);
}
TreeNodehead=helper(0,inorder.length);
returnhead;
}
publicTreeNodehelper(intleft,intright){
if(left==right){
returnnull;
}
introot_val=preorder[count];
TreeNoderoot=newTreeNode(root_val);
count++;
intindex=map.get(root_val);//分离左右子树的界限
root.left=helper(left,index);
root.right=helper(index+1,right);
returnroot;
}
}
