二叉树的前序遍历是：-+abc*def，后序遍历是：bad

[不定项选择题]

二叉树的前序遍历是：-+abc*de/f，后序遍历是：bad*c+f/e-，则层序遍历和中序遍历依次为

查看答案及解析

雨康啊

首先“中序”+“前序”、“中序”+“后序”都能唯一确定一个二叉树是必然的

，但是缺了“中序”就不能唯一确定一棵二叉树也是必然的

发表于 2019-09-19 14:35:31 回复(0)

BiLumi

二叉树是没办法通过前序和后序遍历还原二叉树的，因为没办法确认左右子树，但是这道题是选择题，四个选项中的左右子树数量是一致的，所以可以做。

发表于 2019-07-07 17:01:21 回复(0)

凉风起天末

首先，这道题所给序列中的字符没有实际含义，不能以符号的原本含义来推理本题（因为在尝试将后序序列当作算术表达式的后缀式来进行计算验证时，最终存储操作数的栈未能清空）；

接下来，常规的解题思路当然还是先还原出二叉树，当然只由先、后序遍历序列是不能确定一棵树的，但是我们可以还原出树的大致轮廓，过程如下：

确定树的根节点：“先序的首字符” 和 “后序的尾字符” 相同，为树的根节点；
判断树的左、右子树节点集合：设先序顺序为 "根 - 左右(A)"，后序顺序为 “左右(B) - 根”，则 A 的首字符A-Head为某子树的根节点（如果两子树均存在，它是左树的根，但是如果有一棵子树不存在，那边我们就无法判断它是谁的根），在B序列中找出A-Head的位置，若B中A-Head位于尾部，则说明有一棵子树为空（但是我们无法判断是左还是右，画图时需要以竖直向下的边连接根与子树，表明子树的左右位置无法确定），而若A-Head位于B中间的某个位置，则该位置便是左右子树序列的分界点，左右子树的节点序列由此确定；
递归判断：左右子树的序列与主序列具有相同性质，递归直至确定了叶子节点；

本题还原出来的二叉树结构如下图所示，它的层次遍历序列是确定的，但是中序遍历序列由于无法确定节点b关于a的左右位置，b在左，则b先输出，b在右，则a先输出，所以本题选项A、B均正确：