数据结构+算法(第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为整棵原始二叉树的节点总数。

结束

本文分享自微信公众号 - Java研发军团(ityuancheng)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏慕容千语的架构笔记

Java程序员进阶笔记实操—大型网站架构技术之负载均衡详解(4)

欢迎关注专栏:Java架构技术进阶。里面有大量batj面试题集锦,还有各种技术分享,如有好文章也欢迎投稿哦。

11460
来自专栏C语言入门到精通

编程小白 | 每日一练(153)

这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从编程小白进阶到高手,需要经历的是日积月累的学习,那么如何学习呢?当然是每天都...

11030
来自专栏C语言入门到精通

编程小白 | 每日一练(151)

这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从编程小白进阶到高手,需要经历的是日积月累的学习,那么如何学习呢?当然是每天都...

21840
来自专栏Java架构

如何设计API接口,实现统一格式返回?

在移动互联网,分布式、微服务盛行的今天,现在项目绝大部分都采用的微服务框架,前后端分离方式,(题外话:前后端的工作职责越来越明确,现在的前端都称之为大前端,技术...

43580
来自专栏毛毛v5

golang adodb mssql数据库的query格式化奇葩问题

用adodb驱动查询mssql数据。如果参数带有大括号。就会显示错误: ServeSrs sql db.Prepare error发生意外。 (语法错误或违反...

13440
来自专栏毛毛v5

记录一个assembly: Dependency造成的错误。

一个xamarin.forms工程需要一个Toast来提示信息,大家知道forms没有内置这个简单的控件,不可思议。要自己引入不同平台的实现。于是,偷懒用向导创...

15140
来自专栏C语言入门到精通

编程小白 | 每日一练(149)

这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从编程小白进阶到高手,需要经历的是日积月累的学习,那么如何学习呢?当然是每天都...

12120
来自专栏iOSDevLog

Markdown 自动添加中英文空格

「有研究顯示,打字的時候不喜歡在中文和英文之間加空格的人,感情路都走得很辛苦,有七成的比例會在 34 歲的時候跟自己不愛的人結婚,而其餘三成的人最後只能把遺產留...

14840
来自专栏贺利权

跟着鸡排看世界 AutoEx:v1.0.6 实践

恰巧看到鸡排大大五一更新了一款小神器,瞅着很nice,今天特意玩了一波,感觉很棒~~~

9930
来自专栏吴老师移动开发

Flutter Dart Package开发及发布到pub,实例popup_menu

作为一个开发人员,我们不仅要会用第三方代码,更重要的是能开发出自己的库,供他人使用,在这个过程中可以学到很多东西。

29630

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励