Question

已知某二叉树的先序遍历序列为ABCDEF、中序遍历序列为BADCFE，则可以确定该二叉树（　　）。

A.是单支树（即非叶子结点都只有一个孩子）
B.高度为4（即结点分布在4层上）
C.根结点的左子树为空
D.根结点的右子树为空

Answer 1

【答案】：B
先序遍历即先根后左子树再右子树，中序遍历为先左子树后跟再右子树。先序遍历的最开始结点A即为整棵树的根，结合中序遍历，A结点左侧B即为根节点A的左子树，右侧DCFE则为A的右子树，同理可以得出C为A的右子树的根节点，D为C的左子树，EF为C的右子树，F为E的左子树。可以得到如下图，所以该二颗树的高度为4。

由图可知，叙述符合的只有B选项，树的高度为4。