不务正业之pat解题：1127. ZigZagging on a Tree (30)

[yooocen]

这题一开始我没有想明白，后来发现其实中序的字符串左右子树的长度可以确定后序字符串中左右子树的位置，另一个比较难的是，这里不能用广搜，要用深搜，用一个深度来记录就可以实现

#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=35;
int inorder[maxn];
int postorder[maxn];
int level[maxn][maxn]; //每层的节点id
int levelcnt[maxn]; //每层的节点个数
int maxlayer=0;
int cnt=0; //节点id
struct Node{
    int left=-1,right=-1;
    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-1,postL,postL+lnum-1,tmp,LEFT);
    build(idx+1,inR,postL+lnum,postR-1,tmp,RIGHT);
}
void dfs(int root,int layer){
    if(root==-1)
        return;
    maxlayer=max(layer,maxlayer);
    level[layer][levelcnt[layer]]=root;
    levelcnt[layer]++;
    dfs(node[root].left,layer+1);
    dfs(node[root].right,layer+1);
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>inorder[i];
    for(int i=1;i<=n;i++)
        cin>>postorder[i];
    build(1,n,1,n,-1,-1);
    dfs(1,1);
    bool flag=true;
    printf("%d",node[1].val);
    for(int i=2;i<=maxlayer;i++){
        if(flag){
            for(int j=0;j<levelcnt[i];j++)
                printf(" %d",node[level[i][j]].val);
        }
        else{
            for(int j=levelcnt[i]-1;j>=0;j--)
                printf(" %d",node[level[i][j]].val);
        }
        flag=!flag;
    }
    return 0;
}