L2-006. 树的遍历(重建)

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

#include<bits/stdc++.h>
using namespace std;typedef struct node
{int x;node* left;node* right;
}*tree;
int post[33],in[33];
vector<int> ans;tree rebuild(int* post,int* in,int length)
{if(length==0)return NULL;tree T=(tree)malloc(sizeof(node));T->x=*(post+length-1);int i=0;while(in[i]!=*(post+length-1))i++;T->left = rebuild(post,in,i);T->right = rebuild(post+i,in+i+1,length-i-1);return T;
}void levelorder(tree T)
{queue<tree>q;if(T){q.push(T);while(q.size()){tree tmp=q.front();q.pop();ans.push_back(tmp->x);if(tmp->left)q.push(tmp->left);if(tmp->right)q.push(tmp->right);}}
}int main()
{int n;cin>>n;for(int i=0;i<n;i++)cin>>post[i];for(int i=0;i<n;i++)cin>>in[i];tree t = rebuild(post,in,n);levelorder(t);for(int i=0;i<n-1;i++)printf("%d%c",ans[i],' ');cout<<ans[n-1];
}