Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [,,,,]
inorder = [,,,,]
Return the following binary tree:
/ \
/ \
前序、中序遍历得到二叉树，可以知道每一次前序新数组的第一个数为其根节点。在中序遍历中找到根节点对应下标，根结点左边为其左子树，根节点右边为其右子树，再根据中序数组中的左右子树个数，找到对应的前序数组中的左右子树新数组。设每次在中序数组中对应的位置为i，则对应的新数组为：
前序新数组：左子树[pleft+1,pleft+i-ileft],右子树[pleft+i-ileft+1,pright]
中序新数组：左子树[ileft,i-1],右子树[i+1,iright] C++
TreeNode* buildTree(vector<int>& preorder,int pleft,int pright,vector<int>& inorder,int ileft,int iright){
if(pleft>pright||ileft>iright)
return NULL;
int i=;
for(i=ileft;i<=iright;i++){
if(preorder[pleft]==inorder[i])
break;
}
TreeNode* cur=new TreeNode(preorder[pleft]);
cur->left=buildTree(preorder,pleft+,pleft+i-ileft,inorder,ileft,i-);
cur->right=buildTree(preorder,pleft+i-ileft+,pright,inorder,i+,iright);
return cur;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTree(preorder,,preorder.size()-,inorder,,inorder.size()-);
}