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 = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
本题给定一棵二叉树的前序排列和中序排列，要求构造出这棵二叉树。
前序排列的顺序是：根节点——左节点——右节点
中序排列的顺序是：左节点——根节点——右节点
因此设4个int型值，分别记录当前子树的所有节点在前序、中序数列中位置。
若前序数列中某个值在中序数列中找到，则在中序数列中，前面的值是该节点左子树的所有值（设有m个），后面的值是该节点右子树的所有值（设有n个）。那么，在前序数列中，该值的后m个是它的左子树所有值，m到m+n个是它的右子树的所有值。
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return work(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
}
TreeNode* work(vector<int>& preorder, vector<int>&inorder, int preleft, int preright, int inleft, int inright){
if(preleft>preright) return NULL;
TreeNode *root = new TreeNode(preorder[preleft]);
for(int k=inleft; k<=inright; k++){
if(inorder[k]==preorder[preleft]){
root->left = work(preorder, inorder, preleft+1, preleft+k-inleft, inleft, k-1);
root->right = work(preorder, inorder, preleft+k-inleft+1, preright, k+1, inright);
}
}
return root;
}
};
