专栏首页五分钟学算法五分钟学算法:二叉树的后序遍历

五分钟学算法:二叉树的后序遍历

LeetCode上第145 号问题:二叉树的后序遍历

题目

给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3] 输出: [3,2,1] 进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解题思路

栈(Stack)的思路来处理问题。

后序遍历的顺序为左-右-根,具体算法为:

  • 先将根结点压入栈,然后定义一个辅助结点head
  • while循环的条件是栈不为空
  • 在循环中,首先将栈顶结点t取出来
  • 如果栈顶结点没有左右子结点,或者其左子结点是head,或者其右子结点是head的情况下。我们将栈顶结点值加入结果res中,并将栈顶元素移出栈,然后将head指向栈顶元素
  • 否则的话就看如果右子结点不为空,将其加入栈
  • 再看左子结点不为空的话,就加入栈

动画演示

动画演示GIF加载有点慢,请稍等片刻加载显示^_^

参考代码

补充

下面这种写法使用了一个辅助结点p,这种写法其实可以看作是一个模版,对应的还有前序和后序的模版写法,形式很统一,方便于记忆。上上篇更新前序的和上篇更新的中序文章中都会补充该写法。思路与代码如下:

  • 先将先序遍历的根-左-右顺序变为根-右-左
  • 再翻转变为后序遍历的左-右-根,翻转还是改变结果res的加入顺序
  • 然后把更新辅助结点p的左右顺序换一下即可

本文分享自微信公众号 - 五分钟学算法(blgczzz),作者:菠了个菜

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

原始发表时间:2018-11-17

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 30 张图带你彻底理解红黑树

    小吴正在写红黑树的相关系列文章,不过内容太多,动画做起来比较慢,大家可以先看一下这篇红黑树的介绍,内容很不错。

    五分钟学算法
  • 每天一算:Binary Tree Preorder Traversal

    下面这种写法使用了一个辅助结点p,这种写法其实可以看作是一个模版,对应的还有中序和后序的模版写法,形式很统一,方便于记忆。后续更新的中序和后序文章中都会补充该写...

    五分钟学算法
  • 每天一算:二叉树的中序遍历

    下面这种写法使用了一个辅助结点p,这种写法其实可以看作是一个模版,对应的还有前序和后序的模版写法,形式很统一,方便于记忆。上篇更新前序的和后面要更新后序文章中都...

    五分钟学算法
  • 数据结构 第4讲 单链表

    链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?可以给每个元素附加一个指针域,指向下一个元素的存储位...

    rainchxy
  • 算法基础

    分治法的基本思想: 将一个规模为 n 的问题分解为 k 各规模较小的子问题, 这些子问题互相独立且与原问题是同类型问题。 递归地解这些子问题, 然后把各个子问题...

    yawn
  • 数据结构 第6讲 链栈

    进出的一端称为栈顶(top),另一端称为栈底(base)。栈可以用顺序存储,也可以用链式存储。顺序栈和链栈图解:

    rainchxy
  • Atomwise:与Lilly就AI驱动的药物研发项目达成多年协议

    Atomwise宣布与美国公司Eli Lilly达成一项多年协议,将应用Atomwise的人工智能专利技术,支持Lilly公司的临床前药物研发工作。两家公司将在...

    AiTechYun
  • 详解Linux系统的CPU负载均值

    上一篇文章的最后,作者提到了文章的参考来源,我特意前往访问了下,发现写得非常不错,特转过来,可以结合阅读,以便更容易理解 CPU 负载这个概念。 你可能对于 L...

    张戈
  • linux系统编程之基础必备(七):read/write函数与(非)阻塞I/O的概念

    一、read/write 函数 read函数从打开的设备或文件中读取数据。 #include <unistd.h> ssize_t read(int fd,...

    s1mba
  • 2016 小回顾

    时间很快, 已经走到了 2016 的末尾, 惯例的做个小回顾。(注:这篇起笔的时间是圣诞节TAT)

    Jintao Zhang

扫码关注云+社区

领取腾讯云代金券