【CCCC】L2-011 玩转二叉树 (25分)，二叉树建树与遍历（我讨厌树，@L2-006）

problem

L2-011 玩转二叉树 (25分) 给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式： 输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式： 在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例： 7 1 2 3 4 5 6 7 4 1 3 2 6 5 7 输出样例： 4 6 1 7 5 3 2

二叉树建树，再遍历（我讨厌树，@L2-006）

给出二叉树先序和中序遍历输出镜面反转后的层次遍历

solution

006和011差不多，可见是高频考点我太菜了，强行建树+bfs遍历好了建树：根据中序和前序寻找根结点，再根据根结点递归左右子树继续建树 #include<bits/stdc++.h> using namespace std; const int maxn = 55; int n, pre[maxn], mid[maxn]; struct node{int l, r;}tree[maxn]; int build(int l1, int r1, int l2, int r2){//分别对应中序和先序的左右边界 if(l1 > r1)return 0; int rt = pre[l2], prt = l1;//1.先序确定根 while(mid[prt]!=rt)prt++;//2.中序找根的位置 int cnt = prt-l1;//3.中序确定左子树节点树 //注意在这里反转 tree[rt].r = build(l1,prt-1,l2+1,l2+cnt);//4.递归左子树 tree[rt].l = build(prt+1,r1,l2+cnt+1,r2);//5.递归右子树 return rt; } vector<int>ans; void bfs(int rt){ queue<int>q; q.push(rt); ans.push_back(rt); while(q.size()){ int u = q.front(); q.pop(); if(tree[u].l != 0){ q.push(tree[u].l); ans.push_back(tree[u].l); } if(tree[u].r != 0){ q.push(tree[u].r); ans.push_back(tree[u].r); } } for(int i = 0; i < ans.size()-1; i++) cout<<ans[i]<<" "; cout<<ans[ans.size()-1]; } int main(){ cin>>n; for(int i = 1; i <= n; i++)cin>>mid[i]; for(int i = 1; i <= n; i++)cin>>pre[i]; int root = build(1,n,1,n); bfs(root); return 0; }