若一棵二叉树的前序遍历序列和后序遍历序列分别为1 2 3 4和4 3 2 1 则该二叉树的 中序遍历序列不
遍历,序列,正确答案
已帮助 人
若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的 中序遍历序列不会是
A.1,2,3,4
B.2,3,4,1
C.3,2,4,1
D.4,3,2,1
请帮忙给出正确答案和分析，谢谢！
-
正确答案：C
前序序列为LRN，后序序列为NLR，由于前序序列和后序序列刚好相反，故不可能存在一个结点同时有左右孩子，即二叉树的高度为4.1为根结点，由于根结点只能有左孩子(或右孩子)，因此，在中序序列中，1或在序列首或在序列尾，ABCD皆满足要求。仅考虑以1的孩子结点2为根结点的子树，它也只能有左孩子(或右孩子)，因此，在中序序列中，2或在序列首或序列尾，ABD皆满足要求，故选C。