天梯赛L2-006 树的遍历
L2-006 树的遍历
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数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
我的思路：
关键名词：后序遍历、中序遍历、二叉树、层序遍历
1）给出了后序遍历和中序遍历，所以我们可以推导出这个二叉树的结构，那么我们需要编写一个函数build来构建这个二叉树
（附：因为中序的规律是：root在中间，左边是左子树，右边是右子树
1. 已知前序 + 中序 → 能还原二叉树
2. 已知后序 + 中序 → 能还原二叉树
3.只知道前序 + 后序，不能唯一确定二叉树！
而根据这个特点，我们前序（第一个）、后序（最后一个）遍历来确定根节点，中序遍历来切分左右子树。
2）标准 build 函数思路：
先明确根节点（后序遍历的最后一个）—> 建立一个映射函数mp用来找到根节点在中序遍历中的位置 —>递归build函数，而左右子树的后序遍历的区间，我觉得是里面的一个难点。
左右子树中序遍历的区间很好看出来，因为k是根节点，所以左子树的中序遍历区间就是【il，k-1】，右子树同理；
而这个后序遍历的区间咋看呢？因为中序遍历是左子树—>根—>右子树，后序遍历是左子树—>右子树—>根，所以所以其左子树的pl延续下来，又因为中序遍历和后序遍历的长度肯定是一致的，中序遍历区间长度 = 后序遍历区间长度 = 这棵子树的节点总数，所以其左子树的pr就变成了[pl+(k-1-il)+1]-1；根据中序遍历和后序遍历这个特征，其右子树后序遍历区间的右端点也比较好确认，因为要想走到这个根节点，也就是pr，就要先走到pr-1，而这个pr-1是啥呢？在大脑中模拟一下这个路线，你会发现就是根节点的右子树的根节点。欸这一切又和后序遍历的特征对上了，所以我们轻松地写出了其右子树的右端点为pr-1，而其左端点根据这个区间长度一致可以写出=pr-1+1-（ir-k-1+1)=pr+k-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, pl+k-il-1); if(ir > k) tr[root].r = build(k+1, ir, pl+k-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, pl+k-il-1); if(ir > k) tr[root].r = build(k+1, ir, pr+k-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函数，建好了这个二叉树 */ queue<int> 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; }