Powered by:NEFU AB-IN

Link

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;
  }