1127. ZigZagging on a Tree.md

【PAT A-1127】ZigZagging on a Tree

题意概述

假设二叉树中的所有结点的数据域都是不同的正整数。给出一棵二叉树的后根遍历序列和中根遍历序列，以曲折顺序打印二叉树中所有结点。也就是说，从根结点开始，逐个层次地打印数字，每一层从左到右和从右到左交替打印。

输入输出格式

第一行给出一个正整数 N，表示二叉树中结点的总数。随后第二行给出中根遍历序列，第三行给出后根遍历序列。

以曲折顺序打印二叉树中所有结点。所有数字必须完全由一个空格分隔，并且行尾不得有多余的空格。

数据规模

$$0<N\le3 0$$

算法设计

根据给出的后根遍历序列和中根遍历序列，重建这棵二叉树。然后在层次遍历的基础上进行略微修改，即可按题意要求打印。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
struct BTNode {
    gg val;
    BTNode *left, *right;
    BTNode(gg v, BTNode* l = nullptr, BTNode* r = nullptr) : val(v) {}
};
BTNode* buildTree(vector<gg>& in, vector<gg>& post, gg r, gg left, gg right) {
    if (left > right)
        return nullptr;
    gg i = find(in.begin(), in.end(), post[r]) - in.begin();
    auto root = new BTNode(post[r]);
    root->left = buildTree(in, post, r - 1 - right + i, left, i - 1);
    root->right = buildTree(in, post, r - 1, i + 1, right);
    return root;
}
void levelOrder(BTNode* root) {
    deque<BTNode*> q;  //为方便打印，用deque存储结点指针
    q.push_back(root);
    bool space = false;
    gg level = 0;  //层号，根结点所在层号为1
    while (not q.empty()) {
        gg s = q.size();
        ++level;
        if (level % 2 == 1) {  //层号是奇数，倒序打印本层所有结点
            for (gg i = s - 1; i >= 0; --i) {
                cout << (space ? " " : "") << q[i]->val;
            }
        } else {  //层号是偶数，正序打印本层所有结点
            for (auto i = 0; i < s; ++i) {
                cout << (space ? " " : "") << q[i]->val;
            }
        }
        space = true;
        while (s--) {
            auto t = q.front();
            q.pop_front();
            if (t->left)
                q.push_back(t->left);
            if (t->right)
                q.push_back(t->right);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni;
    cin >> ni;
    vector<gg> post(ni), in(ni);
    for (gg i = 0; i < ni; ++i) {
        cin >> in[i];
    }
    for (gg i = 0; i < ni; ++i) {
        cin >> post[i];
    }
    levelOrder(buildTree(in, post, ni - 1, 0, ni - 1));
    return 0;
}