【题解】牛牛爬树

题意

给你一个长度为的序列，让你构建一棵二叉排序树，然后要求从下到上，从左到右遍历这棵树的节点，并按顺序输出出来。

题解

相当于要求层次遍历从下到上进行遍历，那我们依然可以按正常的层次遍历来做，但是我们记录值的时候也一层一层记录就可以了，所以要求在建树的时候增加一下每个节点所在的层数，在进行正常层次遍历的时候判断一下当前是在那一层即可，最后输出的时候从最后一层开始输出。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct BiTree
{
    int v;
    int dep;
    BiTree *lchild;
    BiTree *rchild;
};
void Insert(BiTree *&T,int v,int dep)
{
    if(T==NULL)
    {
        T=new BiTree;
        T->v=v;
        T->dep=dep;
        T->lchild=NULL;
        T->rchild=NULL;
        return;
    }
    if(T->v>v)
        Insert(T->lchild,v,dep+1);
    else
        Insert(T->rchild,v,dep+1);
}
vector<vector<BiTree*> >ans;
queue<BiTree *>Q;
int main()
{
    int n;
    scanf("%d",&n);
    BiTree *T=NULL;
    for(int i=0; i<n; i++)
    {
        int x;
        scanf("%d",&x);
        Insert(T,x,1);
    }
    while(!Q.empty()) Q.pop();
    Q.push(T);
    vector<BiTree *>tmp;
    while(!Q.empty())
    {
        T=Q.front();
        Q.pop();
        if(tmp.size()==0)
            tmp.push_back(T);
        else if(T->dep==tmp[0]->dep)
            tmp.push_back(T);
        else
        {
            ans.push_back(tmp);
            tmp.clear();
            tmp.push_back(T);
        }
        if(T->lchild!=NULL)
            Q.push(T->lchild);
        if(T->rchild!=NULL)
            Q.push(T->rchild);
    }
    ans.push_back(tmp);
    for(int i=ans.size()-1;i>=0;i--)
    {
        for(int j=0;j<ans[i].size();j++)
            printf("%d ",ans[i][j]->v);
    }
    printf("\n");
    return 0;
}