3384. 二叉树遍历

题意

编写一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
例如如下的先序遍历字符串： abc##de#g##f### 其中 # 表示的是空格，空格字符代表空树。
建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
思路

给出 **先序遍历 + 所有结点（包括空节点）**也可以唯一确定一个二叉树
首先根据先序遍历进行建树
- 注意建树一定要以元素值为下标建树!!!
  再中序遍历进行输出

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-30 11:32:05
* @FilePath: \Acwing\test\test.cpp
* @LastEditTime: 2023-04-18 19:30:13
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e2 + 10, INF = 0x3f3f3f3f;

unordered_map<char, char> l, r;
int id;
string s;

// 根据节点的值进行建树，而不是节点的下标
char dfs()
{
    char rt = s[++id]; // 这句话放哪，取决于是什么遍历
    if (rt == '#' || id >= SZ(s))
        return '1';
    l[rt] = dfs();
    r[rt] = dfs();
    return rt;
}

void dfs2(char root)
{
    if (root == '1')
        return;
    dfs2(l[root]);
    cout << root << " ";
    dfs2(r[root]);
    return;
}

signed main()
{
    cin >> s;
    s = " " + s;

    char root = dfs();
    dfs2(root);
    return 0;
}