Given inorder and postorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.
class Solution {
public:
TreeNode* createTree(vector<int>& inorder,int in_start,int in_end,vector<int>& postorder,int post_start,int post_end)
{
if(in_start>in_end)
return NULL;
int root = postorder[post_end];
int index;
for(int i=in_start;i<=in_end;i++)
{
if(inorder[i] == root)
index = i;
}
int len = index - in_start;
TreeNode* left = createTree(inorder,in_start,index-1,postorder,post_start,post_start+len-1);
TreeNode* right = createTree(inorder,index+1,in_end,postorder,post_start+len,post_end-1);
TreeNode* node = new TreeNode(root);
node->left = left;
node->right = right;
return node;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.size()==0||postorder.size()==0)
return NULL;
return createTree(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
}
};
