AcWing 1497. 树的遍历(传统指针建树)
原题链接
简单
作者:
RanPg
,
2024-03-24 15:20:03
,
所有人可见
,
阅读 3
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef struct Tree{
int val;
Tree *left, *right;
}Tree;
//建树
Tree *build(string str1, string str2)
{
if(str2.empty() || str1.empty()) return NULL;
char c = str1.back();
str1.pop_back();
Tree *root = new Tree();
int index = str2.find(c);
root -> val = c - '0';
//后左 中左
root -> left = build(str1.substr(0, index), str2.substr(0, index));
//后右 中右
root -> right = build(str1.substr(index), str2.substr(index + 1));
return root;
}
void bfs(Tree *root)
{
queue<Tree*> q;
if(root) q.push(root);
while(q.size())
{
auto t = q.front();
q.pop();
cout << (t->val) << " ";
if(t -> left) q.push(t -> left);
if(t -> right) q.push(t -> right);
}
}
int main()
{
int n;
cin >> n;
string str1, str2;
for(int i = 1; i <= n; i ++)
{
int x; cin >> x;
str1.push_back(x + '0');
}
for(int i = 1; i <= n; i ++)
{
int x; cin >> x;
str2.push_back(x + '0');
}
Tree *root = new Tree();
root = build(str1, str2);
bfs(root);
return 0;
}