题32
题目
Q:某二又树的先序序列和后序序列正好相反, 则该二又树一定是 ( ).
A. 空或只有一个结点
B. 高度等于其结点数
C. 任意一个结点无左孩子
D. 任意一个结点无右孩子
分析
A:先序序列是，根左右
后续序列是，左右根
显然那两个序列同时划掉左或者右
也就相反了
我靠，我这种做法怎么失效了，我记得之前有一个题我也是这么做的，是对的
我这种做法也是对的，只不过它换了一个说法
解
B
非空二叉树的先序序列和后序序列相反, 即 “根左右” 与 “左右根” 顺序相反, 因此树只有根结点, 或根结点只有左子树或右子树, 其子树也有同样的性质, 任意结点只有一个孩子, 才能满足先序序列和后序序列正好相反。此时树形应为一个长链, 树中仅有一个叶结点。