哈希表可以在O(1)的时间内找到后序遍历的根结点在中序遍历的位置
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>using namespace std;const int N = 40;int n;
int postorder[N], inorder[N];
unordered_map<int, int> l, r, pos;
int build(int il, int ir, int pl, int pr)
{int root = postorder[pr];int k = pos[root];if (il < k) l[root] = build(il, k - 1, pl, pl + (k - 1 - il));if (k < ir) r[root] = build(k + 1, ir, pl + (k - 1 - il) + 1, pr - 1);return root;
}void bfs(int root)
{queue<int>q;q.push(root);while(q.size()){auto t=q.front();q.pop();cout<<t<<" ";if(l.count(t))q.push(l[t]);if(r.count(t))q.push(r[t]);}
}int main()
{cin >> n;for (int i = 0; i < n; i ++ ) cin >> postorder[i];for (int i = 0; i < n; i ++ ){cin >> inorder[i];pos[inorder[i]] = i;}int root = build(0, n - 1, 0, n - 1);bfs(root);return 0;
}
输出左子树和右子树
for(auto &pl:l){cout<<pl.first<<"->"<<pl.second<<endl;}cout<<endl;for(auto &pr:r){cout<<pr.first<<"->"<<pr.second<<endl;}
