天梯赛L2-006 树的遍历

L2-006 树的遍历给定一棵二叉树的后序遍历和中序遍历请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。输入格式输入第一行给出一个正整数N≤30是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。输出格式在一行中输出该树的层序遍历的序列。数字间以1个空格分隔行首尾不得有多余空格。输入样例72 3 1 5 7 6 41 2 3 4 5 6 7输出样例4 1 6 3 5 7 2我的思路关键名词后序遍历、中序遍历、二叉树、层序遍历1给出了后序遍历和中序遍历所以我们可以推导出这个二叉树的结构那么我们需要编写一个函数build来构建这个二叉树附因为中序的规律是root在中间左边是左子树右边是右子树1. 已知前序 中序 → 能还原二叉树2. 已知后序 中序 → 能还原二叉树3.只知道前序 后序不能唯一确定二叉树而根据这个特点我们前序第一个、后序最后一个遍历来确定根节点中序遍历来切分左右子树。2标准 build 函数思路先明确根节点后序遍历的最后一个— 建立一个映射函数mp用来找到根节点在中序遍历中的位置 —递归build函数而左右子树的后序遍历的区间我觉得是里面的一个难点。左右子树中序遍历的区间很好看出来因为k是根节点所以左子树的中序遍历区间就是【ilk-1】右子树同理而这个后序遍历的区间咋看呢因为中序遍历是左子树—根—右子树后序遍历是左子树—右子树—根所以所以其左子树的pl延续下来又因为中序遍历和后序遍历的长度肯定是一致的中序遍历区间长度 后序遍历区间长度 这棵子树的节点总数所以其左子树的pr就变成了[pl(k-1-il)1]-1根据中序遍历和后序遍历这个特征其右子树后序遍历区间的右端点也比较好确认因为要想走到这个根节点也就是pr就要先走到pr-1而这个pr-1是啥呢在大脑中模拟一下这个路线你会发现就是根节点的右子树的根节点。欸这一切又和后序遍历的特征对上了所以我们轻松地写出了其右子树的右端点为pr-1而其左端点根据这个区间长度一致可以写出pr-11-ir-k-11)prk-ir。先把左边的左子树递归完后返回最底层的左子树的root然后在回到调用build函数的那个位置再次返回其对应的root将左子树都return root完成后再将右子树进行同样的操作。const int N 35; int n; int pos[N], ino[N]; int mp[N]; struct tree{ int l, r; }tr[N]; int build(int il, int ir, int pl, int pr){ int root pos[pr]; int k mp[root]; if(il k) tr[root].l build(il, k-1, pl, plk-il-1); if(ir k) tr[root].r build(k1, ir, plk-il, pr-1); return root; }3层序遍历用BFS就ok了这一步比较简单AC代码献上#include iostream #include queue using namespace std; const int N 35; int n; int pos[N], ino[N]; int mp[N]; struct tree{ int l, r; }tr[N]; int build(int il, int ir, int pl, int pr){ int root pos[pr]; int k mp[root]; if(il k) tr[root].l build(il, k-1, pl, plk-il-1); if(ir k) tr[root].r build(k1, ir, prk-ir, pr-1); return root; } int main(){ cin n; for(int i 1; i n; i ) cin pos[i]; for(int i 1; i n; i ){ cin ino[i]; mp[ino[i]] i; } build(1,n,1,n); int root build(1,n,1,n); /* 作用1把这个二叉树的根节点传给root 2调用了build函数建好了这个二叉树 */ queueint q; q.push(root); bool flag false; while(!q.empty()){ if(!flag) flag true; else printf( ); int t q.front(); q.pop(); printf(%d, t); if(tr[t].l) q.push(tr[t].l); if(tr[t].r) q.push(tr[t].r); } return 0; }