本文共 869 字，大约阅读时间需要 2 分钟。

题目链接：

题目大意：给出中序和后序序列，按照“S”形层序遍历输出。

解题思路：找规律可以发现，只要每次用queue保存，然后遍历了该层的所有结点后，把queue里的结点弹到stack里即可。注意的是，这里需要每次从哪个头开始弹入queue里，需要想好是先 l,r or r,l。

AC 代码

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;struct node{    int d,l,r;}T[40];int n;int in[40], post[40], lvl[40];int create(int l1,int r1, int l2,int r2, int l) // in post{    if(l1>r1) return -1;    lvl[l]++;    int rt=r2;    int p1=l1,p2;    while(in[p1]!=post[r2]) p1++;    p2=p1-l1;    T[rt].d=post[rt];    T[rt].l=create(l1,p1-1,l2,l2+p2-1,l+1);    T[rt].r=create(p1+1,r1,l2+p2,r2-1,l+1);    return rt;}void bfs(int rt){    queue
     
       q;    vector
      
        v;    stack
       
         sk;    q.push(rt);    node nd;    int th=0, cnt=0;    while(v.size()
       
      
     
    
   

转载地址：https://lux-sun.blog.csdn.net/article/details/82148338 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！