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

[tag_link]

参考答案

该树必为单支链：每个结点至多有一个孩子，孩子可以在左侧或右侧；若有 n 个结点，则 height = n。

伪代码

ShapeFromOrders(pre, post):
    n = length(pre)
    if n == 0 or length(post) != n: return INVALID
    if pre != reverse(post): return NOT_THIS_CASE
    return SINGLE_CHAIN, height = n

复杂度

比较序列需 O(n) 时间；若题设已保证两序列互逆，只判断形态可视为 O(1)。双指针比较的额外空间为 O(1)。

边界条件

题设为非空树；n=1 时单个根结点也是单支链。默认结点值可区分，否则仅凭值序列无法逐项识别结点。

易错点

不能进一步断言是全左斜树或全右斜树，单支链的方向可以逐层改变。

评分要点

指出每个结点至多一个孩子；说明左右子树同时存在会破坏逆序关系；给出高度为 n。