题目

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;}
};