Question

某二叉树的先序遍历序列为ABCDEF，中序遍历序列为BADCFE，则该二叉树的高度（即层数）为（　　）。

A.3
B.4
C.5
D.6

Answer 1

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