©2020-2024 ioDraw All rights reserved,
Privacy Policy
1、 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是( )的二叉树。
答：高度等于其节点数
解析：前序遍历顺序是‘M-L-R’，后序遍历的顺序是‘L-R-M’，其中L-R的相对位置不发生变化，变化的是M的位置。题目指出二叉树的先序序列和后序序列结果正好相反：
* 当二叉树只有一个节点时，只有M，L和R为空，满足条件
* 当二叉树为空时，M、L和R均为空，满足条件
* 当二叉树任一节点无左孩子时，L为空，前序遍历为M-R，后序遍历为R-M，结果正好相反，满足条件
* 当二叉树任一节点无右孩子时，R为空，前序遍历的结果为M-L，后序遍历的结果为L-M，满足条件
* 上述分析的四种条件都满足二叉树的高度等于其节点数
2、 一个二叉树的先序遍历结果和中序遍历结果相同，则其所有非叶子节点必须满足的条件是？
解析：此题解析与上题类似，答案为只有右子树
3、 下图为一个二叉树，请选出以下不是遍历二叉树产生的顺序序列的选项
答：B D
解析：
先序遍历结果为（根->左->右）：ABCDEFIGJH
中序遍历结果为（左->右->根）：BDCAIFJGHE
后序遍历结果为（左->右->根）：DCBIJHGFEA
4、一颗二叉树的前序遍历是ABCDFGHE，后序遍历是BGHFDECA，中序遍历是？
答：C
解析：
* 由前序（根左右）第一个字母和后序（左右根）最后一个字母可知根节点为A；
*
中序（左根右），后序（左右根），后序是以B开头的，所以中序应该以B开头；中序（左根右），前序（根左右），前序是以E结尾的，所以中序应该以E结尾，所以选C，B和E之间的顺序不唯一。
* 已知前序遍历和后序遍历无法唯一确定一棵二叉树。根据前序遍历和后序遍历可以确定两棵树：
所以中序遍历结果为BAGFHDCE也是正确的。