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

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

题目

给定一个二叉树,返回它的 后序 遍历。

示例:

输入: [1,null,2,3]

输出: [3,2,1]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解题思路

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

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

  • 先将根结点压入栈,然后定义一个辅助结点head

  • while循环的条件是栈不为空

  • 在循环中,首先将栈顶结点t取出来

  • 如果栈顶结点没有左右子结点,或者其左子结点是head,或者其右子结点是head的情况下。我们将栈顶结点值加入结果res中,并将栈顶元素移出栈,然后将head指向栈顶元素

  • 否则的话就看如果右子结点不为空,将其加入栈

  • 再看左子结点不为空的话,就加入栈

动画演示

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

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

参考代码

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

补充

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

  • 先将先序遍历的根-左-右顺序变为根-右-左

  • 再翻转变为后序遍历的左-右-根,翻转还是改变结果res的加入顺序

  • 然后把更新辅助结点p的左右顺序换一下即可



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



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



五分钟学算法

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

长按识别二维码关注:为您提供更多算法动画解析


本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 五分钟学算法:二叉树的后序遍历

我还会在以下平台发布内容

GitHub 哔哩哔哩