数据结构+算法（第15篇）：“神之一着”与“翻云手”！后序遍历还能这么玩

阅读本文需要5分钟

引言

《精通二叉树的“独门忍术”——线索二叉树（上）》和《精通二叉树的“独门忍术”——线索二叉树（中）》分别介绍了非递归的、不使用堆栈的、空间复杂度为O(1)的中序遍历与前序遍历算法，本文来谈谈非递归的、不使用堆栈的、空间复杂度为O(1)的后序遍历算法。

加上《再不会"降维打击"你就Out了!》介绍的递归的后序遍历算法和非递归的、使用堆栈的后序遍历算法，后序遍历算是凑齐了所有的龙珠，可以召唤神龙了：）

图1 召唤神龙

特别的，《精通二叉树的“独门忍术”——线索二叉树（上）》提到了非递归的、不使用堆栈的、空间复杂度为O(1)的后序遍历算法的两种不同思路：

1. 利用其它遍历方法的线索二叉树来做“后序遍历”；
2. 对原始二叉树做结构改造，以符合前驱或者后继寻址的需要。

本文聚焦第一种思路，下篇文章聚焦第二种思路。

所谓的“其它遍历方法”，无外乎前序遍历和中序遍历。那么问题来了：

是否两种遍历方法的线索二叉树都适合做“后序遍历”？

答案是否定的。原因如下：

根据《精通二叉树的“独门忍术”——线索二叉树（上）》讲到的后序遍历的次序——“左”->“右”->“根”，我们需要有线索能从子树链回根，前序遍历的线索二叉树的线索主要是链回右子树的，不满足这个诉求，只有中序遍历的线索二叉树满足。

“神之一着”

下面的几张图表示了从树根开始“后序遍历”左子树的过程。

其中current指针表示当前位置，蓝色闪电表示该位置进行遍历输出，橙黄色箭头表示current指针移动方向。

第一张图表示的是原始二叉树的形态。

图2 原始二叉树

首先，“神之一着”：添加一个虚拟节点，将它的左孩子指针指向原始二叉树的根节点。

图3 神之一着

这是整个算法中最闪耀的一击！

虽然中序遍历的线索二叉树可以解决子树链回根的问题，但是我们不要忘了：后序遍历的次序是“左”->“右”->“根”，通过中序遍历的线索二叉树只能从“左”回到“根”，不能从“右”回到“根”！

所以很朴素的想法就是：是否能找到一种方法能将“右”回到“根”的问题转换成“左”回到“根”的问题呢？添加了这个虚拟节点之后，原始二叉树的“根”不就到了虚拟节点的“左”侧去了吗？这样不就巧妙地解决了吗？：）

图4 虚拟节点的妙用

接下来，就是老套路，一路向左移动。

边移动，边找前驱节点、“拉线索”。

图5

图6

图7

图8

何时向左移动是尽头呢？

当current指针指向的节点的左孩子为空时。

此时，移动转向，转向current指针指向的节点的右孩子。

图9

图10

当current指针指向的节点是前驱节点的右孩子时，说明对应的局部左子树遍历完了，将左子树输出，并且顺便把之前添加的线索给去掉，以便恢复原始二叉树的形态。

细心的同学，可能会问了：为什么不在上一步就输出，非要等到这一步才开始输出呢？

请比较上一张图和下一张图：

从上一张图到下一张图，current指针的移动方向都是一路向右，如果按照上面同学所想的那样——边向右移动边输出的话，那么在下图current指针指向的位置，就应该输出；但是很可惜，这个位置是局部根节点，它的右子树还没有遍历，根据后序遍历的规则，此时不应该输出。

图11

图12

图13

图14

图15

图16

请注意这一步，蓝色闪电标识的是该步骤要输出信息的节点。

将current指针指向的节点简称为“当前节点”的话，那么上述这些节点就位于当前节点的左孩子到当前节点的前驱节点的这条路径上。

但是这个似乎与图10对应的步骤的输出左子树的描述相互矛盾啊？

“翻云手”

答案如下：

第一：图16这一步的左子树包含了图10那一步的左子树，所以不应该重复输出；

第二：图10的左子树其实是“当前节点的左孩子到当前节点的前驱节点的这条路径”这种描述的一种特例。

综上所述，我们应该以“当前节点的左孩子到当前节点的前驱节点的这条路径”为准。

注意：输出上述这条路径上的节点，要逆序输出——即从当前节点的前驱节点向当前节点的左孩子方向输出。这是由后序遍历的次序决定的。

但是根据树的生产方向，我们只能从左孩子一路向右到前驱节点；要实现逆序输出，我们需要反转父子关系——将这条路径上所有的原始父节点依次变成原始右孩子的右节点。然后就可以根据新的父子关系，一路向右实现逆序输出。输出结束后，再反转一次，就还原成原始路径了。

这就是所谓的“翻云手”算法。

图17 翻云手

具体的代码实现如下：

“全部都到碗里来！”

接下来，将上面所有的步骤翻译成代码，就得到了完整的秘藏算法：

“神之一着、翻云手”算法的时间复杂度

从上面移动轨迹的图示可以看出：

1. 二叉树的每个节点都被经过了2次；
2. 当节点有左子树时，多了找前驱节点的操作；
3. 寻找前驱节点，需要移动的距离d=整棵树的深度H-当前节点的深度h

其中第1点仅涉及2次简单的比较语句，第2、3点涉及(H-h)次比较。

设高度h的节点数目为m，则:

h<H时：m=2^(h-1)
h=H时：1≤m≤2^(h-1)

高度h的所有节点的构建时间开销为

mO(H-h)=O(m(H-h))

若设M=叶子节点总数，则M<=2^(H-1)，整个算法的时间复杂度K为：

K=O(2^(1-1)x(H-1))+
 O(2^(2-1)x(H-2))+……+
 O(M(H-H))

时间复杂度K的表达式与《二叉堆“功夫熊猫”的速成之路》中通过堆调整算法来构造堆的时间复杂度K的表达式一模一样，所以我们可以直接将那里的结论拿来：

K=O(N)

其中N为整棵原始二叉树的节点总数。

结束