https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
本题解法同https://blog.csdn.net/tassardge/article/details/83378692 故不赘述。
C++代码如下，时间复杂度是O(n)，空间复杂度是O(n)。
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
{
if (postorder.empty() || inorder.empty())
return NULL;
map<int, int> inorderMap;
for (int i = 0; i<inorder.size(); i++)
inorderMap[inorder[i]] = i;
return helper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, inorderMap);
}
TreeNode* helper(vector<int>& inorder, int inL, int inR, vector<int>& postorder, int postL, int postR, map<int, int> &inorderMap)
{
if (postL>postR || inL>inR)
return NULL;
TreeNode * root = new TreeNode(postorder[postR]);
int index = inorderMap[root->val];
root->left = helper(inorder, inL, index - 1, postorder, postL, index - inL - 1 + postL, inorderMap);
root->right = helper(inorder, index + 1, inR, postorder, postL + index - inL, postR-1, inorderMap);
return root;
}
};
