PAT甲题题解-1127. ZigZagging on a Tree (30)-中序、后序建树

根据中序遍历和前序遍历确定一棵二叉树，然后按“层次遍历”序列输出。
输出规则：除根节点外，接下来每层的节点输出顺序是：先从左到右，再从右到左，交替输出

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <string>

#include <map>

#define LEFT 0

#define RIGHT 1

using namespace std;

const int maxn=;

int inorder[maxn];

int postorder[maxn];

int level[maxn][maxn]; //每层的节点id

int levelcnt[maxn]; //每层的节点个数

int maxlayer=;

int cnt=; //节点id

struct Node{

    int left=-,right=-;

    int val;

}node[maxn];

//根据中序遍历和后序遍历建立树

void build(int inL,int inR,int postL,int postR,int fa,int LorR){

    if(inL>inR)

        return;

    int val=postorder[postR];

    int idx;

    //在中序遍历中找出父亲节点的索引，其左边是左子树，右边是右子树

    for(int i=inL;i<=inR;i++){

        if(inorder[i]==val){

            idx=i;

            break;

        }

    }

    int lnum=idx-inL;

    cnt++;

    node[cnt].val=val;

    if(LorR==LEFT)

        node[fa].left=cnt;

    else if(LorR==RIGHT)

        node[fa].right=cnt;

    int tmp=cnt;

    build(inL,idx-,postL,postL+lnum-,tmp,LEFT);

    build(idx+,inR,postL+lnum,postR-,tmp,RIGHT);

}

void dfs(int root,int layer){

    if(root==-)

        return;

    maxlayer=max(layer,maxlayer);

    level[layer][levelcnt[layer]]=root;

    levelcnt[layer]++;

    dfs(node[root].left,layer+);

    dfs(node[root].right,layer+);

}

int main()

{

    int n;

    cin>>n;

    for(int i=;i<=n;i++)

        cin>>inorder[i];

    for(int i=;i<=n;i++)

        cin>>postorder[i];

    build(,n,,n,-,-);

    dfs(,);

    bool flag=true;

    printf("%d",node[].val);

    for(int i=;i<=maxlayer;i++){

        if(flag){

            for(int j=;j<levelcnt[i];j++)

                printf(" %d",node[level[i][j]].val);

        }

        else{

            for(int j=levelcnt[i]-;j>=;j--)

                printf(" %d",node[level[i][j]].val);

        }

        flag=!flag;

    }

    return ;

}