点击链接PAT甲级-AC全解汇总
题目：
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Sample Output:
4 1 6 3 5 7 2
题意：
输入二叉树的后序和中序，输出层序
算法笔记的代码：
这道题很早之前看算法笔记的时候就照着打了一遍，先附上算法笔记的代码，再附上我重写的代码
#include<stdio.h>
#include<queue>
using namespace std;
const int maxn=50;
struct node{
int data;node *lchild,*rchild;
};
int pre[maxn],in[maxn],post[maxn];
int n;node* create(int postl,int postr,int inl,int inr){
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(postl,postl+numleft-1,inl,k-1);root->rchild=create(postl+numleft,postr-1,k+1,inr);return root;
}
int num=0;
void BFS(node* root){
queue<node*>q;q.push(root);while(!q.empty()){
node* now=q.front();q.pop();printf("%d",now->data);num++;if(num<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]);}node* root=create(0,n-1,0,n-1);BFS(root);return 0;
}我的思路：
如例子
后序：2 3 1 5 7 6 4
中序：1 2 3 4 5 6 7
手动寻找的思路：
- 从后序找到最后一个 4 ，肯定是根节点，在中序中找根节点 4
- 中序中的根节点 4 切开了左子树和右子树
- 在后序中分别找左子树和右子树的最后一个（即中序4前面的 在后序中最后一个 和 后序的倒数第二个） 1 和 6
- 中序中的 1 和 6 分别切开了左字数和右子树的左右子树
… - 直到第3步找不到点
代码思路：
因为结果是要求层序，所以借用一个队列保存所有的根节点，再依次输出根节点就行，其中第3步需要用两个set记录左右子树的结点
我的代码：
#include<bits/stdc++.h>
using namespace std;int main()
{
int N;cin>>N;int postorder[N]={
0};int inorder[N]={
0};for(int i=0;i<N;i++)cin>>postorder[i];for(int i=0;i<N;i++)cin>>inorder[i];set<int>rooted;deque<int>res;res.push_back(postorder[N-1]);rooted.insert(postorder[N-1]);while(!res.empty()){
//1.在后序中找到的根，直接输出层序int root=res.front();res.pop_front();if(root!=postorder[N-1])cout<<" ";cout<<root;//2.找到根在中序中的位置//根左边的是左子树，右边的是右子树set<int>left_tree,right_tree;int index=N-1,index_root;while(inorder[index--]!=root);index_root=index+1;//找到rootindex=index_root-1;//->root左边,对中序从root往左是左子树while(index>=0&&!rooted.count(inorder[index])){
left_tree.insert(inorder[index]);index--;}index=index_root+1;//->root右边,对中序从root往右是右子树while(index<N&&!rooted.count(inorder[index])){
right_tree.insert(inorder[index]);index++;}//3.在后序中最右的是左右子树的根//从右往左第一个在左子树中的是左子树的根节点index=N-1;while(index>=0&&!left_tree.count(postorder[index]))index--;if(index>=0){
res.push_back(postorder[index]);rooted.insert(postorder[index]);}//从右往左第一个在右子树中的是右子树的根节点index=N-1;while(index>=0&&!right_tree.count(postorder[index]))index--;if(index>=0){
res.push_back(postorder[index]);rooted.insert(postorder[index]);}}return 0;
}感觉还是算法笔记中的易懂些。