二叉树的后序遍历

有空一起学习 2020年2月9日13:57:19 发表评论
文章最后编辑于:2020-2-9 13:58:49

一、后序遍历

后序遍历逻辑:优先访问左、右子节点,然后访问当前节点。

一个后序遍历的示例,它的后序遍历结果为[4, 2, 5, 6, 3, 1]:

二叉树的后序遍历

二、非递归实现

后序遍历的非递归实现比前序和中序的非递归实现要复杂很多,因为每个节点都可能有2个子节点,遍历的时候节点中并没有保存当前的状态,无法确定两个子节点是否已经访问过了。因此,下面采用两个方法来实现非递归访问。

2.1 实现方式一

通过栈+链表配合,流程如下:

  1. 根节点入栈,然后循环遍历访问栈顶元素。
  2. 每访问一个元素,把该元素插入到链表开头,然后分别把左、右子节点压栈。
  3. 循环1-2步,完成后把链表中的节点顺序输出。

代码实现:

2.2 实现方式二

非递归的后序遍历和前、中序遍历一样,也依赖栈这个数据结构,原理:

  1. 把根节点压栈两次,然后循环判断,当栈不为空的时候,取出栈顶元素。
  2. 把取出的栈顶元素和栈当前的栈顶元素对比,如果相等,则把右子节点和左子节点也分别压入栈两次;如果不相等,则访问当前元素。

压栈两次的作用:判断第几次访问节点,第一次访问到节点的时候要先访问子节点,第二次才是访问自己。

一个特别要注意的地方是:栈是先进后出的,所以在压入左右子节点的时候,要先压入右子节点。

代码实现:

三、递归实现

本文共执行62次查询,耗时0.362秒!
历史上的今天
二月
9
有空一起学习

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: