一种新的求二叉树后序遍历的方法！

chloroethylene · 2026-10-20 20:22:44 · 休闲·娱乐

前言

很久以前在做初赛题时想到的，已知前序、中序求后序的方法。请注意本文分区。

正文

前置知识

首先我们知道，二叉树的先序遍历 p 求法为：

在 p 后加入当前节点 u；
递归处理 u 的左子树，没有左儿子则跳过；
递归处理 u 的右子树，没有右儿子则跳过。

同理，中序遍历 m 求法为：

递归处理 u 的左子树，没有左儿子则跳过；
在 m 后加入当前节点 u；
递归处理 u 的右子树，没有右儿子则跳过。

后序遍历 s 求法为：

递归处理 u 的左子树，没有左儿子则跳过；
递归处理 u 的右子树，没有右儿子则跳过；
在 s 后加入当前节点 u。

具体方法

有了上面的铺垫我们就可以发明这一种方法了。

我们定义一棵树的亚硫酸序列 yls 为：

在 yls 后加入当前节点 u；
递归处理 u 的左子树，没有左儿子则跳过；
在 yls 后加入当前节点 u；
递归处理 u 的右子树，没有右儿子则跳过；
在 yls 后加入当前节点 u。

那么我们不难发现这个东西就是前序、中序和后序拼起来的。

所以我们可以从左到右扫描 yls，按照顺序删除 p 中的所有元素，再按照顺序删除 m 中的所有元素。

不难证明一定可以这么操作。那么经过这么操作后留下的序列一定是 s。证明留作课后习题。

删除可以通过打标记实现，那么这样就可以做到 O(n) 求 s 了。

例子

上面的语言描述可能有些不清晰，我们使用一个例子来体会一下。

图中这棵树我们容易求得：

\begin{aligned} p&:1,2,4,7,8,3,5,6\\ m&:7,4,8,2,1,5,3,6\\ s&:7,8,4,2,5,6,3,1\\ yls&:1,2,4,7,7,7,4,8,8,8,4,2,2,1,3,5,5,5,3,6,6,6,3,1 \end{aligned}

我们先在 yls 中删去 p：

yls:\cancel1,\cancel2,\cancel4,\cancel7,7,7,4,\cancel8,8,8,4,2,2,1,\cancel3,\cancel5,5,5,3,\cancel6,6,6,3,1

再删去 m：

yls:\cancel1,\cancel2,\cancel4,\cancel7,\cancel7,7,\cancel4,\cancel8,\cancel8,8,4,\cancel2,2,\cancel1,\cancel3,\cancel5,\cancel5,5,\cancel3,\cancel6,\cancel6,6,3,1

那么剩下的 yls 为：

yls:7,8,4,2,5,6,3,1

就是 s。

能工智人使用说明

本文使用了 human_brain V14 进行写作与润色。