PAT 乙级的一道题目,题目描述:
给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数N(<=30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式:
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。
输入样例: 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 输出样例: 4 1 6 3 5 7 2
原文链接:https://www.patest.cn/contests/gplt/L2-006
一道二叉树的重建类型问题,根据后序遍历的顺序我们可以知道,输出的最后一个节点的值就是整个二叉树的根节点。我们在中序遍历中找到它的位置,那么左右两边的节点就是该节点的左右子树,之后找到后续遍历的倒数第二个节点,这个就是根节点的右子节点,然后再对这个节点进行讨论。。。
如果小伙伴还是不太懂的话,可以参考一下这篇文章,思路原理都是相同的:http://blog.csdn.net/hacker_zhidian/article/details/60770262
Ok,下面给出AC代码:
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = -99999999; // 节点不存在的时候赋值给节点
const int N = 10010;
int in[N];
int post[N];
int pos;
struct Node { // 储存节点信息的结构体
int w; // 值
int l; // 左子节点的下标
int r; // 右子节点的下标
};
Node node[N];
void input(int a[], int n) {
for(int i = 0; i < n; i++) {
cin >> a[i];
}
}
// 重建以第 n 个节点为根节点的二叉树
void rec(int l, int r, int n) {
if(l >= r) {
node[n].w = INF; // 如果节点不存在,赋值为 INF
return ;
}
int root = post[pos--]; // 获取后续遍历中节点的数值
node[n].w = root;
node[n].l = 2*n; // 左子树所在数组下标
node[n].r = 2*n+1; // 右子树所在数组下标
int m = find(in, in+r, root) - in;
rec(m+1, r, 2*n+1); // 因为是后序遍历,所以先重建右子树
rec(l, m, 2*n); // 在重建左子树
}
// 使用 C++ STL 模板提供的队列数据结构
void print() {
queue<int> que;
que.push(1); // 将 1 号节点入队
int index;
while(!que.empty()) {
index = que.front(); // 取出队头元素
que.pop(); // 对头元素出队
if(node[index].w != INF) {
if(index != 1) {
cout << " ";
}
cout << node[index].w;
que.push(node[index].l);
que.push(node[index].r);
}
}
}
int main() {
int n;
cin >> n;
pos = n - 1;
input(post, n);
input(in, n);
rec(0, n, 1);
print();
return 0;
}
如果博客中有什么不正确的地方,还请多多指点。如果觉得我写的不错,请点个赞表示对我的支持吧。
谢谢观看。。。