题目
Leetcode 106. 从中序与后序遍历序列构造二叉树
代码(9.18 首刷自解)
class Solution {
public:
unordered_map<int, int> val2Index;
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
for(int i = 0; i < inorder.size(); i++)
val2Index[inorder[i]] = i;
return build(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);
}
TreeNode* build(vector<int>& inorder, int inL, int inR, vector<int>& postorder, int pL, int pR) {
if(inL > inR || pL > pR)
return nullptr;
auto root = new TreeNode(postorder[pR]);
int index = val2Index[root->val];
int len = index-inL;
root->left = build(inorder, inL, index-1, postorder, pL, pL+len-1);
root->right = build(inorder, index+1, inR, postorder, pL+len, pR-1);
return root;
}
};