题目描述：
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
示例：
给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
解法：
# define PR pair<int, int>
/**
* 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:
int binary_search(vector<PR>& lst, int target){
int l = 0, r = lst.size() -1;
int mid = 0;
while(l <= r){
mid = l + (r-l)/2;
if(lst[mid].first < target){
l = mid + 1;
}else if(lst[mid].first == target){
return lst[mid].second;
}else{
r = mid - 1;
}
}
return -1;
}
// method 3: accepted
TreeNode* buildTree(vector<int>& postorder, vector<int>& inorder, int pl, int pr, int il, int ir, vector<PR>& inlst) {
if(pl > pr){
return NULL;
}else if(pl == pr){
return new TreeNode(postorder[pr]);
}else{
TreeNode* root = new TreeNode(postorder[pr]);
int mid = binary_search(inlst, postorder[pr]);
int lsz = mid - il;
// int rsz = ir - mid;
root->left = buildTree(postorder, inorder, pl, pl + lsz-1, il, il + lsz-1, inlst);
root->right = buildTree(postorder, inorder, pl+lsz, pr-1, il + lsz+1, ir, inlst);
return root;
}
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// method 3:
int sz = postorder.size();
int pl = 0, pr = sz-1;
int il = 0, ir = sz-1;
vector<PR> inlst;
for(int i = 0; i < sz; i++){
inlst.push_back({inorder[i], i});
}
sort(inlst.begin(), inlst.end());
return buildTree(postorder, inorder, pl, pr, il, ir, inlst);
}
};