题意：给定一颗二叉树的后序和中序遍历，给出该树的层序遍历
思路：不必构造二叉树，在先序遍历的时候，把对应下标的节点存入level数组中，在一个二叉树中，下标是唯一确定的，，按照从小到大的顺序访问level数组，即可得到层序遍历，注意一点是由于树可能是一条线，故level数组要开大一点
代码：
#include<iostream> #include<vector> using namespace std; vector<int> post, in, level(100000,-1);//可能有的树为一条线，故下标可能很大 int n = 0, cnt = 0; void pre(int root, int inl,int inr,int index) { if (inl > inr)return; int i = inl; while (i < inr&&in[i] != post[root])i++; level[index] = post[root];//给对应的节点赋予下标 pre(root - (inr - i + 1), inl, i - 1, index * 2 + 1); pre(root - 1, i + 1, inr, index * 2 + 2); } int main() { cin >> n; post.resize(n); in.resize(n); for (int i = 0; i < n; i++) scanf("%d", &post[i]); for (int i = 0; i < n; i++) scanf("%d", &in[i]); pre(n - 1, 0, n - 1, 0); for (int i = 0; i < level.size(); i++) { if (level[i] != -1) { if (cnt != 0)printf(" "); printf("%d",level[i]); cnt++; } if (cnt == n) break;//打印完退出 } system("pause"); return 0; }
