已知后序遍历和中序遍历求层序遍历（树的遍历）

L2-006 树的遍历 (25分)
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 10;
const int inf = 0x3f3f3f3f;
const ll INF = 1ll << 62;
const double PI = acos(-1);
const double eps = 1e-7;
const int mod = 998244353;
#define speed {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); }

int  in[50], post[50];//中序与后序
struct node//建立节点并初始化
{
	int value;
	node *l, *r;
	node(int value = 0, node *l = NULL, node *r = NULL) :value(value), l(l), r(r) {}
};
void buildtree(int l, int r, int &t, node * &root)
{
	int flag = -1;
	for (int i = l; i <= r; i++)
	{
		if (post[t] == in[i])
		{
			flag = i;
			break;
		}
	}
	if (flag == -1)return;
	root = new node(in[flag]);
	t--;//后序数组从后往前（先序数组从前往后）
	if (flag < r)buildtree(flag + 1, r, t, root->r);//已知后序的话先建立右子树
	if (flag > l)buildtree(l, flag - 1, t, root->l);//已知先序的话先建立左子树
}
vector<int>save[50];//用来存储每个深度的节点的值
void dfs(node *root, int deep)
{
	if (root == NULL)return;
	save[deep].push_back(root->value);
	dfs(root->l, deep + 1);
	dfs(root->r, deep + 1);
}
int cnt = 0;
int res[50];
void  inorder(node *root)//输出中序排列（本题不用）
{
	if (root != NULL)
	{
		inorder(root->l);
		res[cnt++] = root->value;
		inorder(root->r);
	}
}
void Free(node *root)//清除空间
{
	if (root != NULL)
	{
		Free(root->l);
		Free(root->r);
		delete root;
	}
	else return;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &post[i]);
	for (int i = 1; i <= n; i++)scanf("%d", &in[i]);
	node *root;
	int t = n;
	buildtree(1, n, t, root);

	/*inorder(root);
	for (int i = 0; i < cnt; i++)
		printf("%d ", res[i]);*/

	dfs(root, 0);
	int f = 0;
	for (int i = 0; i < 50; i++)
	{
		if (save[i].size() == 0)break;//如果读到的层数中无内容说明读完了
		for (int j = 0; j < save[i].size(); j++)
		{
			if (f == 0) { printf("%d", save[i][j]); f = 1; }
			else printf(" %d", save[i][j]);
		}
	}
	Free(root);
	//system("pause");
	return 0;
}

本文地址：https://blog.csdn.net/m0_49041421/article/details/107400135