题目粗心
给定一颗二叉树的中序和后序序列，要求依照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;}