关于c++:PAT甲级1127-ZigZagging-on-a-Tree

题目粗心

给定一颗二叉树的中序和后序序列，要求依照 zigzagging 的形式输入该二叉树的层序遍历

算法思路

首先依据中序和后序遍历序列建设该二叉树，而后在层序遍历中应用 level 记录以后所在档次，每一次将以后层的所有结点都出队到 temp 数组中，更新子节点的 level 并入队，如果 level 是奇数就逆序 temp，而后增加到 ans 数组中保留最终的层序遍历后果，++level。最初输入 ans 数组中的后果即可。

提交后果

AC 代码

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

// 中序，后序和中序序列在 in 数组中的下标
int in[40],post[40],inIndex[40];
int n;// 顶点数目
vector<int> ans;// zigzagging 层序遍历序列

struct Node{int v{};
    int level{};
    Node* left = nullptr;
    Node* right = nullptr;
};

Node* createTree(int postL,int postR,int inL){if(postL>postR){return nullptr;}
    Node* root = new Node;
    root->v = post[postR];
    // 获取根节点在中序遍历中的地位
    int rootIndex = inIndex[root->v];
    // 左子树长度
    int leftSize = rootIndex-inL;
    root->left = createTree(postL,postL+leftSize-1,inL);
    root->right = createTree(postL+leftSize,postR-1,rootIndex+1);
    return root;
}

// level 为偶数从左往右，为奇数从右往左
void layerOrder(Node* root){
    queue<Node*> que;
    root->level = 1;
    que.push(root);
    int level = 1;
    while (!que.empty()){int len = que.size();
        vector<int> temp;
        // 一次性遍历每一层的结点，并保留在 temp 中
        for(int i=0;i<len;++i){Node* t = que.front();
            que.pop();
            if(t->left){
                t->left->level = t->level + 1;
                que.push(t->left);
            }
            if(t->right){
                t->right->level = t->level + 1;
                que.push(t->right);
            }
            temp.push_back(t->v);
        }
        // 档次为奇数得逆序
        if(level%2!=0){reverse(temp.begin(),temp.end());
        }
        for(auto v:temp){ans.push_back(v);
        }
        ++level;
    }
}

int main() {scanf("%d",&n);
    for(int i=0;i<n;++i){scanf("%d",&in[i]);
        inIndex[in[i]] = i;
    }
    for (int i = 0; i < n; ++i) {scanf("%d",&post[i]);
    }
    Node* root = createTree(0,n-1,0);
    layerOrder(root);
    for(int i=0;i<ans.size();++i){printf("%d",ans[i]);
        if(i<ans.size()-1){printf(" ");
        }
    }
    return 0;
}