设有一棵满二叉树（所有结点值均不同），已知其先序序列 pre，设计一个算法求后序序列 post。

[tag_link]

参考答案

满二叉树的左右子树结点数相等。长度为 n 的当前先序片段以根开头，其后各有 m=(n-1)/2 个结点属于左右子树；递归转换后把根写到后序片段末尾。

伪代码

PreToPost(pre, preL, post, postL, n):
    if n == 0: return
    if n == 1:
        post[postL] = pre[preL]
        return
    m = (n - 1) / 2
    subtreeSize = m
    PreToPost(pre, preL + 1,     post, postL,     subtreeSize)
    PreToPost(pre, preL + 1 + m, post, postL + m, subtreeSize)
    post[postL + n - 1] = pre[preL]

复杂度

每个结点写入一次，时间 O(n)；递归栈空间 O(log n)，输出数组 O(n)。

边界条件

n=0 直接返回，n=1 只复制根。输入必须确为满二叉树，故 n=2^h-1；不满足时仅凭先序无法可靠划分子树。

易错点

不能把一般二叉树也按左右各一半切分；根必须最后写入当前后序片段，且右子树的下标偏移要加 m。

评分要点

利用左右 subtreeSize 相等；正确计算 m 和四个区间起点；根写在末尾；说明满二叉树前提。