7-8 树的遍历 (10 分)
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
1. 7 2. 2 3 1 5 7 6 4 3. 1 2 3 4 5 6 7
结尾无空行
输出样例：
4 1 6 3 5 7 2
结尾无空行
#include<iostream> #include<map> using namespace std; int post[100]; int in[100]; map<int,int>m; void pre(int root,int start,int end1,int index){ if(start>end1) return; int i = start; while(i<end1&&post[root]!=in[i]) i++; m[index] = post[root]; pre(root-(end1-i)-1,start,i-1,2*index+1); pre(root-1,i+1,end1,2*index+2); } int main() { int n; cin >> n; for(int i=0; i<n; i++) cin >> post[i]; for(int i=0; i<n; i++) cin >> in[i]; pre(n-1,0,n-1,0); auto it = m.begin(); cout << it->second; while(++it!=m.end()) cout << " " << it->second; return 0; }
#include<iostream> #include<algorithm> #include<unordered_map> #include<vector> #include<queue> using namespace std; const int N=30+10; //记录中序遍历的点 vector<int>inorder(N,0); //记录后序遍历的点 vector<int>postorder(N,0); //记录中序遍历序列每个点的相应位置 第一维表示值 第二维其在中序序列中的具体位置 unordered_map<int,int>pos; //记录原本的树的信息 第一维为表示树结点的值 第二维表示树节点指向的节点 unordered_map<int,int>l,r; //返回值为当前所在节点区间的根 int build(int il,int ir,int pl,int pr){ int root=postorder[pr]; int k=pos[root]; //存在左子树 if(il<k) l[root]=build(il,k-1,pl,pl+(k-1)-il); //存在右子树 if(ir>k) r[root]=build(k+1,ir,pl+(k-1-il)+1,pr-1); /** * 关于递归的区间划分问题 * 很显然递归的目的是进入左右然后再次寻找根 * 所以对于中序遍历很简单结合数轴就可以理解 * 因为k为根节点的位置 所以k左右两边左右子树即对应(il,k-1)(k+1,ir) * 而对于后序遍历则稍微要绕一下 * 由于后序遍历区间的节点数与中序遍历是相等的(这是因为每次划分都是以后序树确定的根为依据) * 所以每次划分后 后序树的左右树也会有与中序树相对应的区间范围 * 即(pl,pl+(k-1)-il)(pl+(k-1-il)+1,pr-1) */ return root; } void bfs(int root){ queue<int>q; q.push(root); while(q.empty()==false){ auto t = q.front(); cout<<t<<' '; q.pop(); if(l.count(t)) q.push(l[t]); if(r.count(t)) q.push(r[t]); } } int main(){ int n; cin>>n; for(int i=0;i<n;i++) cin>>postorder[i]; for(int i=0;i<n;i++){ cin>>inorder[i]; pos[inorder[i]]=i; } int root=build(0,n-1,0,n-1); bfs(root); return 0; }
#include<iostream> #include<queue> using namespace std; typedef struct node *tree; struct node{ int data; tree l,r; }; tree build(int in[],int post[],int n){ if(!n)return NULL; int i; for(i=0;i<n;i++)if(in[i]==post[n-1])break; tree t=(tree)new(tree); t->data=post[n-1]; t->l=build(in,post,i); t->r=build(in+i+1,post+i,n-i-1); return t; } const int N=40; int post[N],in[N]; int n; int main(){ cin>>n; for(int i=0;i<n;i++)cin>>post[i]; for(int i=0;i<n;i++)cin>>in[i]; tree t=build(in,post,n); queue<tree>leve; leve.push(t); int f=0; while(!leve.empty()){ tree root=leve.front(); leve.pop(); if(f++)cout<<' '; cout<<root->data; if(root->l)leve.push(root->l); if(root->r)leve.push(root->r); } return 0; }
