甜品店网站开发背景,做美食教程的网站有哪些,广州建筑设计公司有哪些,wordpress5.0先序遍历#xff1a;根-左-右 序列的第一个数就是根
中序遍历#xff1a;左-根-右 知道中间某一个数为根#xff0c;则这个数的左边就是左子树#xff0c;右边则是右子树
后序遍历#xff1a;左-右-根 序列的最后一个数就是根
题目
给定一棵…先序遍历根-左-右 序列的第一个数就是根
中序遍历左-根-右 知道中间某一个数为根则这个数的左边就是左子树右边则是右子树
后序遍历左-右-根 序列的最后一个数就是根
题目
给定一棵二叉树的后序遍历和中序遍历请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式
输入第一行给出一个正整数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 1e124;
int post[M], in[M];
int position[N]; //记录中序遍历的每个点的下标位置
vectorint a(N, -1); //用来装中序遍历的结果待筛选
vectorint 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-head1)个数前面有(index-head)个数后面有(tail-index)个数 int index position[post[root]] ;/*下面这一部分可能不是很好理解大家可以在纸上画一下*/ //左子树 /*左子树的root隔了右子树的个数1这么多个数的那个1是root范围就是:head~index-1 */build(root-(tail-index1), head, index-1, idx*2);//开始右子树/*右子树的根的位置在root-1 中序遍历的范围锁定index的右边index1 ~ tail中序遍历根的序号为idx*21 */ build(root-1, index1, tail, idx*21);
}
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;
}
