根据二叉树的前序和中序构建树，并按层次输出（C++）vector存树

L2-006 树的遍历

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
int po[35];
int ino[35];
vector<int>ans[50];
 
 
int  dfs(int l1, int r1, int l2, int r2) {
	for (int i = l2; i <= r2; i++) {
		if (ino[i] == po[r1]) { 
			int root = po[r1]; 
 
			int lc = dfs(l1, l1 + i - l2 - 1, l2, i - 1) ; //递归左子树
			int rc = dfs(l1 + i - l2, r1 - 1, i + 1, r2) ; //递归右子树
			if (lc) ans[root].push_back(lc); //存进对应的根中
			if (rc) ans[root].push_back(rc);//同上
 
			return root;
		}
	}
	return 0;
 
 
}
 
 
void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> po[i];
	for (int i = 1; i <= n; i++) cin >> ino[i];
	dfs(1, n, 1, n);
 
	queue<int>q;
	q.push(po[n]);
	cout << po[n];
	while (q.size()) {
		int t = q.front();
		q.pop();
		for (auto i : ans[t]) {
			q.push(i);
			cout << " " << i;
		}
 
 
	}
 
 
 
 
}
 
 
signed main() {
 
	int t = 1;
	// cin>>t;
	while (t--) solve();
 
	return 0;
}