问题 O: 基础实验4-2.3：二叉树的非递归遍历

你是一名高级算法工程师，在对抗三体入侵的未来计划中，你被冰冻送往未来继续写代码……苏醒后你被分配到了未来人类社会的巨大地下树形公寓住宅大楼。

你居住的公寓是棵二叉树，每个房间就像一片叶子。在挑选房间时你得知： 

1. 除大楼底层的根结点外，住进的房间必须保证父节点已有人居住；
2. 空的房间会被居委会标记为“#”（不含引号）；
3. 居住在其中的每位房客，会按各自的喜好用一个字符给房间取名，但不能取为“#”。

为了统计居民的数据，居委会想请你帮忙给这栋楼写一个代码：按前、中、后序遍历二叉树的顺序，输出各个有住客的房间名称。

输入只有一行，是“前序遍历”这栋树形公寓后的结果，无人居住的房间用“#”表示，字符之间用空格隔开。

例子：图中的公寓最后呈现为：A B D # # F E # # # C G # H # # I # # 

输出三行： 中、前、后序遍历的结果，房间名用空格隔开

A B D # # F E # # # C G # H # # I # #

Inorder:D B E F A G H C I
Preorder:A B D F E C G H I
Postorder:D E F B H G I C A