1020 Tree Traversals (25分)
1020
分析：
给了中序遍历和后序遍历，输出层次遍历。
1.先根据中序遍历和后序遍历重建二叉树：采用递归的方式重建二叉树。初始时后序遍历的最后一个结点就是根结点，在中序遍历中找到根结点之后，左子树区间和右子树区间就可以确定了。
递归终止的条件是区间长度小于0。
2.然后再进行层次遍历。
C++:
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 31;
struct Node {
int data;
Node *lchild, *rchild;
};
int in[maxn], post[maxn];
int n, cnt = 0;
Node *create(int inL, int inR, int postL, int postR) {
if (postL > postR) {
return NULL;
}
Node *root = new Node;
root->data = post[postR];
int k;
for (k = inL; k <= inR; k++) {
if (in[k] == post[postR]) {
break;
}
}
int numLeft = k - inL;
root->lchild = create(inL, k - 1, postL, postL + numLeft - 1);
root->rchild = create(k + 1, inR, postL + numLeft, postR - 1);
return root;
}
void levelOrder(Node *root) {
queue<Node *> q;
q.push(root);
while (!q.empty()) {
Node *now = q.front();
q.pop();
printf("%d", now->data);
cnt++;
if (cnt < n) {
printf(" ");
}
if (now->lchild != NULL) {
q.push(now->lchild);
}
if (now->rchild != NULL) {
q.push(now->rchild);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &post[i]);
}
for (int i = 0; i < n; i++) {
scanf("%d", &in[i]);
}
levelOrder(create(0, n - 1, 0, n - 1));
return 0;
}
