PAT甲级1127 ZigZagging on a Tree 层序遍历

Dear 丶 2023-02-21 06:08 11阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70][]

#  思路： #

层序遍历然后输出，要求是遍历顺序是不同深度采用不同的顺序（假设第二层是从左到右，那么第三层就是从右往左）

其实只需要给每个结点加一个深度信息，由于层序遍历必然同一深度在一块区间，因此将每个区间分开保存，上一层是从左到右，那么当前层是从右到左输出（反转一下即可）

具体操作就是按照常规层序遍历，但是输出是相同层数的保存在一起，同一层的按照当前层数的输出规则输出

# 代码 #

#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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200628204712319.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw==,size_16,color_FFFFFF,t_70