Home PAT 1127 ZigZagging on a Tree
Post
Cancel

PAT 1127 ZigZagging on a Tree

Link

事实上, 边建树就可以边存储. 每次 build 都针对一个根节点 post[postRight], 并且这些节点都是按照 depth 从左向右遍历的 (标准的层序遍历). 最后, 根据层号的奇偶性判断输出顺序即可.

注意, 在判断 i&1==0 时要写成 (i&1)==0, 因为 & 的优先级很低. 总之, 只要涉及到 &, <<, >> (移位操作符优先级也很低) 的全都打上括号肯定不会错.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,maxDepth;
int in[35],post[35];
vector<int>ans[35];
void build(int inLeft,int inRight,int postLeft,int postRight,int depth){
    if(inLeft>inRight||postLeft>postRight) return;
    maxDepth=max(maxDepth,depth);
    int i=inLeft;
    for(;i<=inRight;++i)
        if(in[i]==post[postRight])
            break;
    ans[depth].push_back(in[i]);
    build(inLeft,i-1,postLeft,postLeft+(i-inLeft-1),depth+1);
    build(i+1,inRight,postLeft+(i-inLeft),postRight-1,depth+1);
}
int main() {
    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]);
    build(1,n,1,n,1);
    for(int i=1;i<=maxDepth;++i){
        if(i!=1) printf(" ");
        if(i&1){
            for(int j=ans[i].size()-1;j>=0;--j){
                if(j!=ans[i].size()-1) printf(" ");
                printf("%d",ans[i][j]);
            }
        }else{
            for(int j=0;j<ans[i].size();++j){
                if(j!=0) printf(" ");
                printf("%d",ans[i][j]);
            }
        }
    }
    printf("\n");
    return 0;
}
This post is licensed under CC BY 4.0 by the author.