PAT甲級1127 ZigZagging on a Tree 層序周遊

 思路：

層序周遊然後輸出，要求是周遊順序是不同深度采用不同的順序（假設第二層是從左到右，那麼第三層就是從右往左）

其實隻需要給每個結點加一個深度資訊，由于層序周遊必然同一深度在一塊區間，是以将每個區間分開儲存，上一層是從左到右，那麼目前層是從右到左輸出（反轉一下即可）

具體操作就是按照正常層序周遊，但是輸出是相同層數的儲存在一起，同一層的按照目前層數的輸出規則輸出

代碼

#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
struct node{
    int data;
    node *l,*r;
    int level;
};
struct r{
    int data;
    int le;
};
vector<int> post,in;
vector<r> v;
map<int,int> bst;
void built(node* &root,int data)
{
    if(root==NULL)
    {
        root=new node;
        root->l=NULL;root->r=NULL;
        root->data=data;
        return;
    }
    else 
    {
        if(bst[data]<bst[root->data])built(root->l,data);
        else built(root->r,data);
    }
}
void levelorder(node* rot)
{
    queue<node*> q;
    rot->level=0;
    q.push(rot);
    while(!q.empty())
    {
        node* it=q.front();
        v.push_back({it->data,it->level});
        //cout<<it->data<<" ";
        q.pop();
        if(it->l!=NULL)
        {
            it->l->level=it->level+1;q.push(it->l);
        }
        if(it->r!=NULL)
        {
            it->r->level=it->level+1;q.push(it->r);
        }
    }
}
int main()
{
    int n,cnt=1;
    cin>>n;
    in.resize(n);
    post.resize(n);
    for(int i=0;i<n;i++){cin>>in[i];bst[in[i]]=i;}
    for(int i=0;i<n;i++)cin>>post[i];
    reverse(post.begin(),post.end());
    node* rot=NULL;
    for(int i=0;i<n;i++)built(rot,post[i]);
    levelorder(rot);
    cout<<v[0].data;
    vector<int> temp;
    for(int i=1,j;i<v.size();)
    {
        for(j=i;j<v.size();j++)
        {
            if(v[j].le==cnt)temp.push_back(v[j].data);
            else break;
        }
        i=j;
        if(cnt%2==0)reverse(temp.begin(),temp.end());
        //輸出
        for(int k=0;k<temp.size();k++)cout<<" "<<temp[k];
        cnt++;
        temp.clear();
    }
    return 0;
}