一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( )。

Question

A.其中任意一个结点均无左孩子
B.其中任意一个结点均无右孩子
C.其中只有一个叶结点
D.其中最多只有一个度为2的结点

Answer 1

【答案】：C
先序遍历的次序是“根左右”，后序遍历的次序是“左右根”，若此二叉树任一结点都没左孩子，则先序遍历次序演变为“根右”，后序遍历的次序是“右根”，两序列正好相反。或者若此二叉树任一结点都没右孩子，则先序遍历次序演变为“根左”，后序遍历的次序是“左根”，两序列也相反。因此，我们可以知道选项A、B均满足题意。然而我们将上述两个条件合并考虑，可以得出，如果二叉树的任一结点或者没有左孩子，或者没有右孩子时，先序遍历序列与后序遍历序列相反，实际上就是此二叉树必须为单支树。而单支树的特点就是只有一个叶结点。