先序遍历:根-左-右 => 序列的第一个数就是根
中序遍历:左-根-右 => 知道中间某一个数为根,则这个数的左边就是左子树,右边则是右子树
后序遍历:左-右-根 => 序列的最后一个数就是根
题目
给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数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 N= 1e5 + 24, inf = 1e9 + 7, M = 1e1+24;
int post[M], in[M];
int position[N]; //记录中序遍历的每个点的下标位置
vector<int> a(N, -1); //用来装中序遍历的结果(待筛选)
vector<int> ans; //最后的结果
// 解释一下参数含义:
/*
root:根在后序遍历中的位置,从n开始
head-tail:中序遍历的范围是从1-n开始的
idx:层次遍历的下表, 用a[idx] 来记录的,
但是a不是最终的结果,因为这不是一棵完全二叉树,我把a都置为-1了,只有非-1才是我们的结果,后面会处理的,先不管
*/
void build(int root, int head, int tail, int idx)
{
if(tail < head) return; //到叶子了,回溯
a[idx] = post[root] ; //先把根记录下来
//找到根在中序遍历的位置,index之前的数就是左子树,之后的数就是右子树
// 一共有(tail-head+1)个数,前面有(index-head)个数,后面有(tail-index)个数
int index = position[post[root]] ;
/*下面这一部分可能不是很好理解,大家可以在纸上画一下*/
//左子树
/*
左子树的root隔了右子树的个数+1这么多个数,+的那个1是root
范围就是:head~index-1
*/
build(root-(tail-index+1), head, index-1, idx*2);
//开始右子树
/*
右子树的根的位置在root-1
中序遍历的范围锁定(index的右边):index+1 ~ tail
中序遍历根的序号为idx*2+1
*/
build(root-1, index+1, tail, idx*2+1);
}
int main()
{
int n, i, j , k;
// memset(a, -1, sizeof(a));
cin >> n;
// 二叉树的后序遍历
for(i = 1; i <= n; i ++)
{
cin >> post[i];
}
// 二叉树的中序遍历
for(i = 1; i <= n; i ++)
{
cin >> in[i];
//position用来 记录各个值在中序遍历中的位置,后面会用到
// 这里假设键值都是互不相等的正整数,依据这个条件,如果有重的元素就不行了哈
position[in[i]] = i;
}
//build里面的参数含义见上方函数定义
build(n, 1, n, 1);
for(i = 0; i < a.size(); i ++)
{
if(a[i] != -1)
{
ans.push_back(a[i]);
}
}
for(i = 0; i < ans.size(); i ++)
{
if(i > 0) cout << " ";
cout << ans[i];
}
return 0;
}