题目描述
blablabla
bfs+dfs(30ms)
bfs找点,dfs寻找每层的点数,
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <cstring>
using namespace std;
const int N = 350000;
int n, maxDepth;
int l[N], r[N], pos[N], q[N], res[N], cnts[N];
int inorder[N], postorder[N];
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 - il + k - 1);
if (k < ir) r[root] = build(k + 1, ir, pl - il + k, pr - 1);
return root;
}
void bfs(int root) {
int hh = 0, tt = 0;
q[0] = root;
int cnt = 0;
while (hh <= tt) {
int t = q[hh++];
res[cnt++] = t;
if (l[t] != -1) q[++tt] = l[t];
if (r[t] != -1) q[++tt] = r[t];
}
}
void dfs(int u,int depth) {
if (u == -1) return;
cnts[depth]++;
if (depth > maxDepth) maxDepth = depth;
dfs(l[u], depth + 1);
dfs(r[u], depth + 1);
}
int main() {
cin >> n;
memset(r, -1, sizeof r);
memset(l, -1, sizeof l);
for (int i = 0; i < n; i++) {
cin >> inorder[i];
pos[inorder[i]] = i;
}
for (int i = 0; i < n; i++) cin >> postorder[i];
int root = build(0, n - 1, 0, n - 1);
bfs(root);
dfs(root, 0);
int begin = 0;
bool f = true;
for (int i = 0; i <= maxDepth; i++){
if (f) for (int j = begin + cnts[i] -1 ; j >= begin; j--) cout << res[j] << " ";
else for (int j = begin; j < begin + cnts[i]; j++) cout << res[j] << " ";
begin += cnts[i];
f = !f;
}
}
dfs (199ms)
dfs
blablabla
时间复杂度
参考文献
在dfs时直接加入vector,运行比dfs+bfs慢
C++ 代码
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <cstring>
using namespace std;
const int N = 350000;
int n, maxDepth;
int l[N], r[N], pos[N], q[N], res[N];
int inorder[N], postorder[N];
vector<int> cnt[N];
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 dfs(int u,int depth) {
if (u == 0) return;
cnt[depth].push_back(u);
if (depth > maxDepth) maxDepth = depth;
dfs(l[u], depth + 1);
dfs(r[u], depth + 1);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> inorder[i];
pos[inorder[i]] = i;
}
for (int i = 1; i <= n; i++) cin >> postorder[i];
int root = build(1, n , 1, n );
dfs(root, 0);
for (int i = 0; i <= maxDepth; i++) {
auto& v = cnt[i];
if (i % 2 == 0) for (int i = v.size() - 1; i >= 0; i--) cout << v[i] << ' ';
else for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
}
}