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

内存限制:512 MB 时间限制:2.000 S
评测方式:文本比较 命题人:
提交:29 解决:16

题目描述

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

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

  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

来源/分类