题目描述

将树上元素按照Z字形输出，  通过队列获取某一层元素存入vector<int> res;的方式

while(q.size()){
    int size=q.size();
    for(int i=0;i<size;i++){
        auto t=q.front();q.pop();
        res.push_back(t);
        if(l[t]) q.push(l[t]);
        if(r[t]) q.push(r[t]);
    }

}

算法1

C++ 代码

#include<iostream>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;
const int N=40;

int midorder[N],postorder[N];
map<int,int> l,r,position;

int n;
//通过vector存储输出序列
vector<int> res;


int build(int ml,int mr,int pl,int pr){
    int root=postorder[pr];
    int k=position[root];
    if(k>ml){
        //递归构建左子树
        l[root]=build(ml,k-1,pl,pl+k-1-ml);

    }
    if(k<mr){
        //递归构建右子树
        r[root]=build(k+1,mr,pl+k-ml,pr-1);
    }

    return root;
}

void bfs(int root){

    queue<int> q;
    q.push(root);
    bool flag=true;//标记是否进行翻转
    while(q.size()){
        //首先获取这里层的元素个数
        int size=q.size();//获取层序遍历每一层元素的方式
        for(int i=0;i<size;i++){
            int t =q.front();q.pop();
            res.push_back(t);//将该层元素存入序列
            //按照层次序入队
            if(l.count(t)){//将下一层元素入队
                q.push(l[t]);
            }
            if(r.count(t)){
                q.push(r[t]);
            }
        }
        //此时队列中元素为下一层所有元素
        //判断是否需要逆序
        if(flag){
            //对这里层元素逆序，新加入的这一层size个元素
            reverse(res.end()-size,res.end());
        }
        flag=!flag;
    }

}

int main(){
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>midorder[i];
        position[midorder[i]]=i;
    }

    for(int i=1;i<=n;i++){
        cin>>postorder[i];
    }

    int root=build(1,n,1,n);

    //打印Z字形
    bfs(root);

    //output
    for(int i=0;i<res.size();i++){
        cout<<res[i]<<" ";
    }

    return 0;
}