[PAT解题报告] Tree Traversals

```#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

struct node {
node *left;
node *right;
int x;
};

node a[100];
int m,po[100],in[100];

node* make(int *po, int *in, int length) {
if (length == 0) {
return 0;
}
node *root = &a[m++];
int i;
for (i = 0; in[i] != po[length - 1]; ++i)
;
root->x = in[i];
root->left = make(po, in, i);
root->right = make(po + i, in + i + 1, length - 1 - i);
return root;
}

int main() {
int n;
scanf("%d",&n);
for (int i = 0; i < n; ++i) {
scanf("%d",po + i);
}
for (int i = 0; i < n; ++i) {
scanf("%d",in + i);
}
node *root = make(po, in, n);
if (root) {
bool have = false;
queue<node *> q;
q.push(root);
node *last = root;
while (!q.empty()) {
bool out = false;
node *next;
while (!out) {
node *temp = q.front();
q.pop();
if (temp == last) {
out = true;
}
if (temp->left) {
q.push(next = temp->left);
}
if (temp->right) {
q.push(next = temp->right);
}
if (have) {
putchar(' ');
}
else {
have = true;
}
printf("%d",temp->x);

}
last = next;
}
}
puts("");
return 0;
}

```

2022-12-06 16:44

2022-12-14 17:48

2022-12-09 16:06

2022-12-12 18:42

2022-12-08 20:03

2022-12-14 15:52

2022-12-03 16:23

2022-12-07 15:22

2022-12-10 13:31

2022-12-06 13:45

2022-12-16 11:40

2022-12-13 21:48