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