7-11 玩转二叉树 (25 分)
给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
1. 7 2. 1 2 3 4 5 6 7 3. 4 1 3 2 6 5 7
结尾无空行
输出样例：
4 6 1 7 5 3 2
结尾无空行
#include<bits/stdc++.h> using namespace std; typedef struct node *tree; struct node { int data; tree l,r; }; int in[40] ,pre[40] ,n; tree build(int pre[] ,int in[] ,int n) { if (n == 0) return NULL; int i; while(i<n&&in[i]!=pre[0]) i++; tree t = (tree) new (tree); t -> data = in[i]; t -> l = build (pre + 1 ,in ,i); t -> r = build (pre + i + 1 ,in + i + 1 ,n - i - 1); return t; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> in[i]; for (int i = 0; i < n; i++) cin >> pre[i]; tree t = build(pre ,in ,n); queue<tree>q; q.push(t); int f = 0; while (!q.empty()) { tree x = q.front(); q.pop(); if (f++) cout << ' '; cout << x -> data; if (x -> r) q.push(x -> r); if (x -> l) q.push(x -> l); } return 0; }
#include<iostream> using namespace std; #include<cstring> const int N=40,inf=-1,M=1e5; int n,in[N],pre[N],leve[M],flag; void dfs(int root,int s,int d,int idx){ if(s>d)return ; int i=s; while(s<d&&in[i]!=pre[root])i++; leve[idx]=pre[root]; dfs(root+1,s,i-1,2*idx+2); dfs(root+(i-s+1),i+1,d,2*idx+1); } int main(){ cin>>n; memset(leve,inf,sizeof leve); for(int i=0;i<n;i++)cin>>in[i]; for(int i=0;i<n;i++)cin>>pre[i]; dfs(0,0,n-1,0); for(int i=0;i<M;i++){ if(leve[i]!=-1){ if(flag)cout<<' '; cout<<leve[i]; flag=1; } } return 0; }
