C++题解：二叉树（见证成长）

题目

题解：

知识点：

分析：

代码：

题目

1000ms
131072K

给定一个二叉树的中序遍历序列和前序遍历序列，先将树左右翻转（对于每个非叶结点，左右子树互换），然后输出翻转后树的层序遍历。二叉树每个结点的值不同。
输入格式
第一行一个整数 N(1≤N≤30) ，表示二叉树结点个数。

第二行 N 个整数，表示二叉树的中序遍历序列。

第三行 N 个整数，表示二叉树的前序遍历序列。

二叉树每个结点的值为不超过 10^9 的正整数。
输出格式
输出一行，包含 N 个整数，表示翻转后二叉树的层序遍历序列。

格式说明

输出时每行末尾的多余空格，不影响答案正确性

输入、输出要求

要求使用「文件输入、输出」的方式解题，输入文件为 binary.in，输出文件为 binary.out

样例输入
3
2 1 3
1 2 3
样例输出
1 3 2

题解：

知识点：
树、大模拟

分析：
直接模拟

注意：

所谓翻转，其实就是将原来层序遍历的从左到右遍历的顺序改为从右到左（初三的我）。当然也可以傻傻模拟一遍（六年级的我）。
节点数字很大，数组开不下，可以用离散化（六年级的我）。不过用哈希表代替儿子数组更简便一些（初三的我）

代码：

//六年级
#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 35;
long long a[N], b[N], son[N][2],d[N];
queue q;
mapmp;
void dfs(int x1,int y1,int x2){
    int pos=b[x2];
    int len1=pos-x1,len2=y1-pos;
    if (len1>0){
        son[b[x2]][0]=b[x2+1];
        dfs(x1,pos-1,x2+1);
    }
    if (len2>0){
        son[b[x2]][1]=b[x2+len1+1];
        dfs(pos+1,y1,x2+len1+1);
    }
}
int n;
int main() {
    freopen("binary.in","r",stdin);
    freopen("binary.out","w",stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]]=i;
        d[i]=a[i];
        a[i]=i;//这是干啥？
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        b[i]=mp[b[i]];//这是干啥？
    }
    dfs(1, n, 1);
    for (int i=1;i<=n;i++){
        swap(son[i][0],son[i][1]);
    }
    q.push(b[1]);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout< 
 and 
//初三
#include
#include
#include
#include
#include
#define _for(i,a,b) for (int i=(a);i<=(b);i++)
using namespace std;
typedef long long LL;
const int N=35;
LL a[N],b[N];//,son[N][2]
unordered_map> son;
inline void c_plus(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void dfs(int x1,int y1,int x2){
    int pos=x1;
    while (a[pos]!=b[x2]){
        pos++;
    }
    int len1=pos-x1,len2=y1-pos;
    if (len1){
        son[b[x2]].first=b[x2+1];
        dfs(x1,pos-1,x2+1);
    }
    if (len2){
        son[b[x2]].second=b[x2+1+len1];
        dfs(pos+1,y1,x2+1+len1);
    }
}
int main(){
    freopen("binary.in","r",stdin);
    freopen("binary.out","w",stdout);
    c_plus();
    int n;
    cin>>n;
    _for(i,1,n){
        cin>>a[i];
    }
    _for(i,1,n){
        cin>>b[i];
    }
    dfs(1,n,1);
    queue q;
    q.push(b[1]);
    while (!q.empty()){
        LL u=q.front();
        q.pop();
        cout<

C++题解：二叉树（见证成长）

题解：

知识点： 树、大模拟

C/C++/C#相关栏目本月热门文章

知识点：
树、大模拟