题目描述

2025年4月18日
思路：树的遍历
题意：已知二叉树的前序遍历(带有空节点位置)求中序遍历

算法1

别人的代码非常简洁，一边“建树”，一边输出

时间复杂度

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

void build()
{
    char ch = getchar();
    if(ch == '#')
        return ;

    build();
    cout << ch << ' ';
    build();
}

int main()
{
    build();
    return 0;
}

算法2

我的代码和他的代码虽然算法是一致的，但是我花了一些时间，下次要统计时间了

C++ 代码

#include<bits/stdc++.h>
using namespace std;

void dfs(string s,int* n,int root){
    if(s[*n]=='#')
    return;
    (*n)++;
    dfs(s,n,*n);
    cout << s[root]<<' ';
    (*n)++;
    dfs(s,n,*n);
}
int main(){
    string s;
    int n=0;
    cin >> s;
    dfs(s,&n,0);
    return 0;
}