根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
思路
先序序列的第一个节点是根节点，凭此去遍历中序序列，得到中序遍历根节点的位置，于是可以从中序遍历得出左右子树的结点数，再以同样的方式去递归求出左子树结点和右子树结点
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder,inorder,0,0,inorder.length-1);
}
public TreeNode build(int[] pre, int[] in,int preL,int inL,int inR){
// if(inL == inR) return new TreeNode(pre[preL]);
if(inL>inR){
return null;
}
TreeNode root=new TreeNode(pre[preL]);
int k=0;
for(int i=inL;i<=inR;++i){
if(in[i]==pre[preL]){
k=i;
break;
}
}
int numLeft=k-inL;
root.left=build(pre,in,preL+1,inL,k-1);
root.right=build(pre,in,preL+numLeft+1,k+1,inR);
return root;
}
}
