完全二叉树的层序遍历（模板）以及树的其他类型题

传送门
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是完美二叉树。对于深度为 D 的，有 N 个结点的二叉树，若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点，这样的树就是完全二叉树。

给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历结果。

输入格式：
输入在第一行中给出正整数 N（≤30），即树中结点个数。第二行给出后序遍历序列，为 N 个不超过 100 的正整数。同一行中所有数字都以空格分隔。

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

输入样例：
8
91 71 2 34 10 15 55 18
输出样例：
18 34 55 71 2 10 15 91

题解：首先知道是完全二叉树，然后对于知道的后序遍历，我们就可以每次从后面处理它，先处理右节点，再处理左节点，那么我们就应该开一个标记数组，用来去处理他的每个结束遍历的叶子节点的条件。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mse(a,b) memset(a,b,sizeof a)
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=1e9+7;
const int maxx=1e6+10;
const double eps=1e-6;
using namespace std;
const long double PI = 3.14159265358979323846;
//inline ll read(){ ll x=0,f=1; char ch=getchar(); while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); } while (isdigit(ch)) { x=x*10+ch-48;  ch=getchar();  } return x*f;}
//ll cc = ((1ll << 62) - 1 + (1ll << 62));
/*struct node {
    ll l,r ,lazy,val;
    node() :l(),r(),lazy(),val(){}
    node(ll a, ll b, ll c,ll d) :l(a),r(b),lazy(c),val(d){}

};
*/
int n,p;
int ans[3000],vis[maxx];
int cmp[maxx];
void dfs(int x)
{
    if(!vis[x])
    {
        cmp[x]=ans[p--];
        vis[x]=1;
    }
    if(!vis[2*x+1]) dfs(x<<1|1);
    if(!vis[x<<1]) dfs(x<<1);
}
signed main()
{
    for(int i=1; i<=3000; i++)vis[i]=1;cin>>n;p=n;
    for(int i=1; i<=n; i++)cin>>ans[i],vis[i]=0;
    dfs(1);cout<<cmp[1];
    for(int i=2; i<=n; i++)
    {
        cout<<" "<<cmp[i];
    }
    cout<<endl;
    return 0;
}

由于自己对树的遍历理解很差 所以以此来复习

传送门
题解：包含空节点（“#”），这个数是一颗满二叉树；
正常去遍历 然后记录他的深度

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mse(a,b) memset(a,b,sizeof a)
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=1e9+7;
const int maxx=1e6+10;
const double eps=1e-6;
using namespace std;
const long double PI = 3.14159265358979323846;
//inline ll read(){ ll x=0,f=1; char ch=getchar(); while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); } while (isdigit(ch)) { x=x*10+ch-48;  ch=getchar();  } return x*f;}
//ll cc = ((1ll << 62) - 1 + (1ll << 62));
/*struct node {
    ll l,r ,lazy,val;
    node() :l(),r(),lazy(),val(){}
    node(ll a, ll b, ll c,ll d) :l(a),r(b),lazy(c),val(d){}
 
};
*/
char ans[300];
int dou[maxx];
int sum=0;
void dfs(int x)
{
 
    if(ans[sum]!='#')
    {
    if(sum<strlen(ans))
        {
        dou[sum]=x;
    sum++;
    dfs(x+1);
    sum++;
    dfs(1+x);
    }
    }
}
signed main(){
   while(~scanf("%s",ans)&&ans[0]!='#')
   {
       sum=0;
       mse(dou,0);
       dfs(0);
       for(int i=0;i<strlen(ans);i++)
       {
            if(ans[i]!='#')
            {
                for(int j=1;j<=3*dou[i];j++)
                    cout<<" ";
                cout<<ans[i]<<endl;
            }
       }
        cout<<endl;
   }
 
   return 0;
}

传送门

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mse(a,b) memset(a,b,sizeof a)
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod=1e9+7;
const int maxx=1e6+10;
const double eps=1e-6;
using namespace std;
const long double PI = 3.14159265358979323846;
//inline ll read(){ ll x=0,f=1; char ch=getchar(); while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); } while (isdigit(ch)) { x=x*10+ch-48;  ch=getchar();  } return x*f;}
//ll cc = ((1ll << 62) - 1 + (1ll << 62));
/*struct node {
    ll l,r,lazy,val;
    node() :l(),r(),lazy(),val(){}
    node(ll a, ll b, ll c,ll d) :l(a),r(b),lazy(c),val(d){}
 
};
*/
char ans[300];
void dfs(int x,int k)
{
   // cout<<x<<" "<<k<<endl;
    if(x<=k){
    if(ans[x]!='#')
        cout<<ans[x];
        dfs(x<<1,k);
        dfs(x<<1|1,k);
    }
}
void dfs1(int x,int k)
{
    if(x<=k)
    {
       dfs1(x<<1,k);
        if(ans[x]!='#')
            cout<<ans[x];
       dfs1(x<<1|1,k);
    }
}
void dfs2(int x,int k)
{
    if(x<=k)
    {
        dfs2(x<<1,k);
        dfs2(x<<1|1,k);
        if(ans[x]!='#')
        {
            cout<<ans[x];
        }
    }
}
signed main(){
   while(~scanf("%s",ans+1))
   {
       dfs(1,strlen(ans+1));
       cout<<endl;
       dfs1(1,strlen(ans+1));
       cout<<endl;
       dfs2(1,strlen(ans+1));
       cout<<endl<<endl;;
   }
 
   return 0;
}
 

对于一个二层树（深度为1）来讲

先序遍历：
树根在先，左，右叶子，从上到下,从左到右
中序遍历：
左叶子，根节点，右叶子，从下到上，从左到右
后序遍历：
左右叶子，根节点，从下到上，从左到右

先后中是指根的位置
遍历的叶子节点是子树的话要完成整个子树的遍历才算完成此节点
借图