PAT甲级 1127 Z 字形遍历二叉树

原题链接

假设一个二叉树上各结点的权值互不相同。

我们就可以通过其后序遍历和中序遍历来确定唯一二叉树。

请你输出该二叉树的 Z 字形遍历序列----也就是说，从根结点开始，逐层遍历，第一层从右到左遍历，第二层从左到右遍历，第三层从右到左遍历，以此类推。

例如，下图所示二叉树，其 Z 字形遍历序列应该为：1 11 5 8 17 12 20 15。

 

输入格式
第一行包含整数 N，表示二叉树结点数量。

第二行包含 N 个整数，表示二叉树的中序遍历序列。

第三行包含 N 个整数，表示二叉树的后序遍历序列。

输出格式
输出二叉树的 Z 字形遍历序列。

数据范围
1≤N≤30
输入样例：
8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1
输出样例：
1 11 5 8 17 12 20 15

我的解法：

#include 
using namespace std;
const int N = 40;
unordered_map  l, r, pos;
int post[N], in[N], q[N];
int build(int il, int ir, int pl, int pr){
    int root = post[pr];
    int k = pos[root];
    if(il < k) l[root] = build(il, k - 1, pl, pl + k - 1 -il);
    if(k < ir) r[root] = build(k + 1, ir, pl + k - il, pr - 1);
    return root;
}
void bfs(int root){
    q[0] = root;
    int hh = 0, tt = 0;
    int step = 0;
    while(hh <= tt){
        int head = hh, tail = tt;
        while(hh <= tail){   // 用while一层一层处理
            int t = q[hh ++]; // 队头出队
            if(l.count(t)) q[ ++ tt] = l[t]; //让队头相关元素进队
            if(r.count(t)) q[ ++ tt] = r[t]; //让队头相关元素进队
        }
        if(++ step % 2 ) reverse(q + head, q + tail + 1);
    }
}
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++ ){
        cin >> in[i];
        pos[in[i]] = i;
    }
    for(int i = 0; i < n; i ++ ){
        cin >> post[i];
    }
    int root = build(0, n-1, 0, n-1);
    bfs(root);
    
    cout << q[0];
    for (int i = 1; i < n; i ++ ) cout << ' ' << q[i];
    cout << endl;
    return 0;
}

 收获：

此题本质上还是考察二叉树遍历，我们用bfs进行层序遍历，在层序遍历的过程中，如果要分层处理，可以嵌套while循环，进行分层处理！