/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(0 == inorder.size() || 0 == postorder.size()) return NULL;
return build(inorder, postorder, postorder.size() - 1, inorder.begin(), inorder.end());
}
TreeNode *build(vector<int>& inorder, vector<int>& postorder, int postStartIndex,
vector<int>::iterator inStart, vector<int>::iterator inEnd){
if(postStartIndex < 0 || inStart >= inEnd) return NULL;
auto temp = find(inStart, inEnd, postorder[postStartIndex]);
if(temp == inorder.end())
return NULL;
else{
TreeNode *root = new TreeNode(postorder[postStartIndex]);
root->right = build(inorder, postorder, postStartIndex - 1, temp+1, inEnd);
root->left = build(inorder, postorder, postStartIndex - (inEnd - temp), inStart, temp);
return root;
}
}
};
