基于前缀字符串构建二叉树

【题目网址：https://www.nowcoder.com/questionTerminal/4b91205483694f449f94c179883c1fef

编写一段程序，用于读取用户输入的一串先序遍历字符串，并依据该字符串构建一个二叉树（采用指针方式存储）。例如，如下所示的先序遍历字符串： ABC##DE#G##F### 其中，“#”符号代表空格，空格字符表示空树。构建完该二叉树之后，再对其进行中序遍历，并输出相应的遍历结果。
例如

输入：abc##de#g##f###
输出：c b e g d f a

其中，空格字符串代表的是空树。

实际上，这道题的含义是：给出一棵二叉树的先序遍历结果，然后根据该结果构建出对应的二叉树，并输出其对应的中序遍历结果。
如果仅有先序遍历的结果，我们无法唯一确定这棵树的结构。
那么如何才能重建一棵完整的二叉树呢？

• 提供中序遍历的结果和先序遍历的结果
• 提供中序遍历的结果和后序遍历的结果

但本题具有一定的特殊性，因为它使用“#”来表示空树，从而可以成功重建这棵树。
以题目中的例子：

abc##de#g##f###
利用这个字符串还原出一棵树的过程与先序遍历的方式一致，即首先递归地创建左子树，再递归地创建右子树。
在这个例子