B1127 ZigZagging on a Tree (树的建立

B1127 ZigZagging on a Tree (30分)

//简单模板题，思维量不大，手速要快！！！

• 建树，已知中序，后序

两序建树

• 判断是否能继续进行
  if(left>right)
  return;
• 新建根结点，找寻根节点的值和位置
• 递归左子树和右子树
• 返回根节点

• 推层序

层序记录当前结点的深度，vt存放当前层的顺序数

• 输出

奇数2k-1层的放在vt[2k-1]逆向输出，偶数2k层的放在vt[2k]正向输出

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define lowbit(i)((i)&(-i))
using namespace std;
typedef long long ll;
const int MAX=50;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const int SQR=633;
int in[MAX],post[MAX];
int k=0;
struct node
{
    node* lchild;
    node* rchild;
    int data;
    int height;
};
vector<int>vt[MAX];
void bfs(node* root)
{
    queue<node*>q;
    root->height=1;
    q.push(root);
    while(!q.empty())
    {
        node* top=q.front();
        q.pop();
        k=max(k,top->height);
        vt[top->height].push_back(top->data);
        if(top->lchild!=NULL)
        {
            top->lchild->height=top->height+1;
            q.push(top->lchild);
        }
        if(top->rchild!=NULL)
        {
            top->rchild->height=top->height+1;
            q.push(top->rchild);
        }
    }
}
node* create(int inl,int inr,int postl,int postr)
{
    if(postl>postr)
        return NULL;
    node* root=new node;
    root->data=post[postr];
    int i;
    for(i=inl;i<=inr;i++)
    {
        if(in[i]==post[postr])
            break;
    }
    int numleft=i-inl;
    root->lchild=create(inl,i-1,postl,postl+numleft-1);
    root->rchild=create(i+1,inr,postl+numleft,postr-1);
    return root;
}
int main()
{
   int n;
   scanf("%d",&n);
   for(int i=1;i<=n;i++)
   {
       scanf("%d",&in[i]);
   }
   for(int i=1;i<=n;i++)
   {
       scanf("%d",&post[i]);
   }
    node* a=create(1,n,1,n);
    bfs(a);
    printf("%d",vt[1][0]);
    for(int i=2;i<=k;i++)
    {
        if(i%2!=0)
        {
            for(int j=vt[i].size()-1;j>=0;j--)
                printf(" %d",vt[i][j]);
        }
        else
        {
            for(int j=0;j<vt[i].size();j++)
                printf(" %d",vt[i][j]);
        }
    }
    return 0;
}