[数据结构与算法]个人练习-PAT甲级-1127 ZigZagging on a Tree

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805349394006016

题目大意：给出二叉树的中序和后序遍历。求特殊的层序遍历：设第0层为根，那么奇数层从左往右遍历，偶数层从右向左遍历。

思路：虽然N<=30，但是考虑到skewing tree的情况，用数组可能很深。所以用类建树。

class Node{
public:
    int val, lvl;
    Node *left, *right;
    Node() {
        left = right = nullptr;
    }
};

先根据中序和后序得到二叉树。

Node* build(int s1, int t1, int s2, int t2) {
    if (s1 > t1 || s2 > t2)
        return nullptr;

    int root = post[t2];
    int ptr = t1;
    while (in[ptr] != root)
        ptr--;
    Node* tmp = new Node();
    tmp->val = root;
    tmp->left = build(s1, ptr-1, s2, s2+(ptr-s1)-1);
    tmp->right = build(ptr+1, t1, t2-(t1-ptr), t2-1);

    return tmp;
}

随后DFS确定每个节点所在的层数

void DFS(Node* p, int lv) {
    if (p == nullptr)
        return ;
    p->lvl = lv;
    DFS(p->left, lv+1);
    DFS(p->right, lv+1);
}

先正常层序遍历。每层的结果存在一个对应的数组里

void zigzag() {
    queue<Node*> q;
    Node* ptr = tree;
    q.push(tree);
    while (!q.empty()) {
        if (q.front()->left)
            q.push(q.front()->left);
        if (q.front()->right)
            q.push(q.front()->right);
        ret[q.front()->lvl].push_back(q.front()->val);
        q.pop();
    }
}

输出。奇数层正常输出，偶数层倒着输出。

    printf("%d", ret[0][0]);
    int lv = 1;
    while (ret[lv].size()) {
        if (lv % 2 != 0) {
            for (int i = 0; i < ret[lv].size(); i++)
                printf(" %d", ret[lv][i]);
        }
        else {
            for (int i = ret[lv].size()-1; i >= 0; i--)
                printf(" %d", ret[lv][i]);
        }
        lv++;
    }

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>


using namespace std;


class Node{
public:
    int val, lvl;
    Node *left, *right;
    Node() {
        left = right = nullptr;
    }
};


int N;
vector<int> in;
vector<int> post;
vector<int> ret[31];
Node* tree = nullptr;


Node* build(int s1, int t1, int s2, int t2) {
    if (s1 > t1 || s2 > t2)
        return nullptr;

    int root = post[t2];
    int ptr = t1;
    while (in[ptr] != root)
        ptr--;
    Node* tmp = new Node();
    tmp->val = root;
    tmp->left = build(s1, ptr-1, s2, s2+(ptr-s1)-1);
    tmp->right = build(ptr+1, t1, t2-(t1-ptr), t2-1);

    return tmp;
}


void DFS(Node* p, int lv) {
    if (p == nullptr)
        return ;
    p->lvl = lv;
    DFS(p->left, lv+1);
    DFS(p->right, lv+1);
}


void zigzag() {
    queue<Node*> q;
    Node* ptr = tree;
    q.push(tree);
    while (!q.empty()) {
        if (q.front()->left)
            q.push(q.front()->left);
        if (q.front()->right)
            q.push(q.front()->right);
        ret[q.front()->lvl].push_back(q.front()->val);
        q.pop();
    }
}


int main() {
    scanf("%d", &N);
    in.resize(N);
    post.resize(N);

    for (int i = 0; i < N; i++)
        scanf("%d", &in[i]);
    for (int i = 0; i < N; i++)
        scanf("%d", &post[i]);

    tree = build(0, N-1, 0, N-1);
    DFS(tree, 0);
    zigzag();

    printf("%d", ret[0][0]);
    int lv = 1;
    while (ret[lv].size()) {
        if (lv % 2 != 0) {
            for (int i = 0; i < ret[lv].size(); i++)
                printf(" %d", ret[lv][i]);
        }
        else {
            for (int i = ret[lv].size()-1; i >= 0; i--)
                printf(" %d", ret[lv][i]);
        }
        lv++;
    }

    return 0;
}