若某二叉树的后序遍历序列为KBFDCAE，中序遍历序列为BKEFACD，则该二叉树为（ ）。
- A.见图A
- B.见图B
- C.见图C
- D.见图D
正确答案及解析
正确答案
A
解析
本题考查二叉树的遍历。
二叉树的主要遍历方式有：前序遍历、中序遍历、后序遍历、层次遍历。如果已知中序遍历，并知道前序遍历与后序遍历中的任意一个，便可得到一棵唯一的二叉树。
具体是怎么做的呢？
利用的是遍历的特点。中序遍历的顺序是：左、根、右。而后序遍历的顺序是：左、右、根。
回到题目里面来，从“后序遍历序列为KBFDCAE”，可以得知，二叉树的根结点为：E（此时已经可以排除选项C与选项D了）。继续分析，由“中序遍历序列为BKEFACD”，可以得知，二叉树的左子树包括结点：BK。右子树包括结点：FACD。
重复上面的步骤，对左子树与左子树看成独立的两棵树进行分析。在后序遍历中，左子树的结点BK的顺序为“KB”，所以B是根结点；右子树的结点FACD的顺序为“FDCA”，所以右子树的根结点为A。当分析到这一步时，已经可以得到本题答案为A。
