C1084 - 重建二叉树
题目描述
对二叉树的先序遍历的方式是，先访问根，然后先序遍历左子树，再先序遍历右子树，简单来说就是：根、左子树、右子树
上面图示的一棵二叉树的先序遍历结果是：ABDC
如果仅知道一棵二叉树的先序遍历结果，比如ABDC，是无法唯一确定一棵二叉树的形态的，比如，下面的二叉树的先序遍历结果也为ABDC
仅通过上面的先序遍历结果无法确定一棵二叉树的形态主要是因为不知道空节点的信息，比如BD，B为根，D既可以是左子树节点也可以是右子树节点
通常需要同时知道一棵二叉树的先序遍历结果和中序遍历结果或者中序遍历和后序遍历结果才能唯一确定一棵二叉树的形态
除了同时知道二叉树的先序遍历结果和中序遍历结果可以唯一确定一棵二叉树外，还有一种扩展的先序遍历也可以唯一确定一棵二叉树的形态
这里对第一张图的二叉树进行扩展成下图：
扩展的方式是：将原来的二叉树中每个空节点使用一个特殊的节点去表示，即图中虚线表示的#节点，扩展后的二叉树的先序遍历结果就可以唯一确定一棵二叉树了
上图扩展后的二叉树的先序遍历结果为：AB#D##C##，仅通过这个先序遍历的结果是可以唯一确定一棵二叉树的形态的，因为扩展后的二叉树中包含了明确的空节点的信息，消除了空节点的歧义
现在给出扩展后的二叉树的先序遍历结果（每个二叉树节点中包含一个唯一的大写英文字母，#节点代表的是原二叉树中的空节点），请你编写后程序重建原二叉树，然后输出该原二叉树的中序遍历、后序遍历、层次遍历结果以及该原二叉树的高度
输入格式、
一行字符串，代表扩展后的二叉树的先序遍历结果，输入的都是合法的遍历结果
输出格式
第1行，原二叉树的中序遍历结果，每个二叉树节点信息之间不需要使用空格分隔
第2行，原二叉树的后序遍历结果，每个二叉树节点信息之间不需要使用空格分隔
第3行，原二叉树的层次遍历结果，每个二叉树节点信息之间不需要使用空格分隔
第4行，原二叉树的高度（根节点的高度为1）
输入输出样例
| 输入样例 | 输出样例 |
|---|---|
| AB#D##C## | BDAC DBCA ABCD 3 |
数据范围与提示
对于100%的数据满足：字符串长度 <= 20
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式