2013-11-09 20:23:03Morris
[其他題目] 由中根序列和后根序列重建二叉树
- 前序走訪
- 給定中序走訪、後序走訪
- 描述
我们知道如何按照三种深度优先次序来周游一棵二叉树，来得到中根序列、前根序列和后根序列。反过来，如果给定二叉树的中根序列和后根序 列，或者给定中根序列和前根序列，可以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列，要求在内存中重建二叉树，最后输出这棵二叉树的前根序列。
用不同的整数来唯一标识二叉树的每一个结点，下面的二叉树
中根序列是9 5 32 67
后根序列9 32 67 5
前根序列5 9 67 32
- 输入
- 两行。第一行是二叉树的中根序列，第二行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0～65535。暂不必考虑不合理的输入数据。
- 输出
- 一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点之间用空格隔开。
- 样例输入
9 5 32 67 9 32 67 5
- 样例输出
5 9 67 32
之前沒有記錄到這一題，記錄一下。
#include <stdio.h>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
int parseInt(int a[], char s[]) {
int n = 0;
stringstream sin(s);
while(sin >> a[n])
n++;
return n;
}
int Idx, cidx = 0;
int a[1024], b[1024], c[1024];
void dfs(int l, int r) {
if(l > r)
return;
int i, j = l;
for(i = l; i <= r; i++) {
if(a[i] == b[Idx]) {
j = i;
break;
}
}
Idx--;
dfs(j+1, r);
dfs(l, j-1);
c[cidx++] = a[j];
}
int main() {
char s[1024];
int i, j, k, n;
while(gets(s)) {
n = parseInt(a, s);
gets(s);
n = parseInt(b, s);
Idx = n-1, cidx = 0;
dfs(0, n-1);
for(i = cidx-1; i >= 0; i--) {
if(i != cidx-1)
putchar(' ');
printf("%d", c[i]);
}
puts("");
}
return 0;
}