题目

https://www.patest.cn/contests/pat-a-practise/1020

题意：给定二叉树的后序、中序遍历结果，输出其层次遍历结果

解题思路

首先重建树，关于利用含中序的两种序列构建这棵二叉树，详见之前的博客二叉树遍历（已知前中序求后序），最后根据这棵树的层次做输出，一遍BFS就可以解决。

AC代码

#include <iostream> #include <queue> #include <cstdlib> using namespace std; const int maxn = 35; int n, posOrder[maxn], midOrder[maxn]; typedef struct node { int value; node *left, *right; }NODE; //s1/e1为后序字符串的首尾,s2/e2为中序字符串首尾 NODE* BuildTree(int s1, int e1, int s2, int e2) { NODE* newnode = (NODE*)malloc(sizeof(NODE)); newnode->value = posOrder[e1]; newnode->left = newnode->right = NULL; int cmp = posOrder[e1], rootIndex = -1; for (int i = s2; i<=e2; ++i) //找到中序序列中的当前根节点对应下标 { if (midOrder[i] == cmp) { rootIndex = i; break; } } //注意下面递归式参数的计算 if (rootIndex != e2) //该节点有右子树 newnode->right = BuildTree(e1-(e2-rootIndex), e1-1, rootIndex+1, e2); if (rootIndex != s2) //该节点有左子树 newnode->left = BuildTree(s1, e1-(e2-rootIndex)-1, s2, rootIndex-1); return newnode; } void BFS(NODE *root) { vector<int> res; queue<NODE> q; NODE tmp; q.push(*root); while(!q.empty()) { int sz = q.size(); for (int i = 0; i<sz; ++i) //遍历当前层结点 { tmp = q.front(); q.pop(); res.push_back(tmp.value); //由该节点产生下一层的结点 if (tmp.left != NULL) q.push(*tmp.left); if (tmp.right != NULL) q.push(*tmp.right); } } for (int i = 0; i < res.size(); ++i) //层次输出 { cout << res[i]; if (i != res.size()-1) cout << ' '; else cout << endl; } } int main() { cin >> n; for (int i = 0; i<n; ++i) cin >> posOrder[i]; for (int i = 0; i<n; ++i) cin >> midOrder[i]; NODE* root = BuildTree(0, n-1, 0, n-1); BFS(root); return 0; }