若某非空二叉树的先序序列和后序序列正好相同，则该二叉树的形态是什么？

[tag_link]

参考答案

在结点值互异且二叉树非空的前提下，该树仅有一个根结点。只要存在第二个结点，先序首项是根而后序首项必不是根，两序列就不可能相同。

伪代码

ShapeWhenEqual(pre, post):
    if length(pre) != length(post) or pre != post: return NOT_THIS_CASE
    if size(T) == 1: return ONLY_ROOT
    return IMPOSSIBLE

复杂度

逐项比较需 O(n) 时间，额外空间 O(1)。

边界条件

空树也会得到两个空序列，但题目明确非空；n=1 时成立。结点值应能唯一标识结点。

易错点

不要把“先序与后序不能唯一确定一般二叉树”误用到本题；这里要求两个完整序列逐项相同。

评分要点

利用根在先序首位、后序末位；排除 n>1；得出仅有一个根结点。