若一棵二叉树的先序遍历序列和后序遍历序列分别为1234和4321，则该二叉树的中序遍历序列可能是( )。

admin2020-01-17 65

问题若一棵二叉树的先序遍历序列和后序遍历序列分别为1234和4321，则该二叉树的中序遍历序列可能是( )。

选项 A、1234
B、2341
C、3241
D、4321

答案A,B,D

解析已知先序遍历序列和中序遍历序列，或者已知后序遍历序列和中序遍历序列，可以唯一地确定一棵二叉树。根据该二叉树的先序遍历序列，如果该二叉树的中序遍历序列是A项，可以确定的二叉树如下图(a)所示。同理，根据B、C、D三项确定的二叉树分别如下图(b)、(e)、(d)所示。在这四棵二叉树中，只有图(c)的后序遍历序列为342l，故只有C项不可能是该二叉树的中序遍历序列。