[PAT解题报告] Tree Traversals
给定二叉树的后序和中序遍历，返回它的层序遍历。
分析： （1） 先还原二叉树。
因为节点数很少，我们可以用一个大的全局数组代替指针变量——当然每个节点的左右孩子还是指针变量，只不过它们的值指向大数组里的元素，而不是真正自己从堆里开辟的空间。还原可以递归进行。
后序遍历序列最后一个字符x是根节点 (R)x
中序遍历找到对应的x (A)x(B)，
它被切分为(A)、(B)两部分，分别对应左右子树。从后序遍历序列的(R)中切分出(A)和(B)那么长的两段，对应于左右子树的后序遍历序列。然后递归还原左右子树即可。
还原出二叉树，做层序遍历时，只需要进行bfs就可以了。
代码：
#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;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1020
查看5道真题和解析
投递中国中铁等公司9个岗位 >