五分钟学算法:二叉树的后序遍历
16lz
2021-01-22
题目
给定一个二叉树,返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
输出: [3,2,1]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
解题思路
用栈(Stack)的思路来处理问题。
后序遍历的顺序为左-右-根,具体算法为:
先将根结点压入栈,然后定义一个辅助结点head
while循环的条件是栈不为空
在循环中,首先将栈顶结点t取出来
如果栈顶结点没有左右子结点,或者其左子结点是head,或者其右子结点是head的情况下。我们将栈顶结点值加入结果res中,并将栈顶元素移出栈,然后将head指向栈顶元素
否则的话就看如果右子结点不为空,将其加入栈
再看左子结点不为空的话,就加入栈
动画演示
动画演示GIF加载有点慢,请稍等片刻加载显示^_^
参考代码
补充
下面这种写法使用了一个辅助结点p,这种写法其实可以看作是一个模版,对应的还有前序和后序的模版写法,形式很统一,方便于记忆。上上篇更新前序的和上篇更新的中序文章中都会补充该写法。思路与代码如下:
先将先序遍历的根-左-右顺序变为根-右-左
再翻转变为后序遍历的左-右-根,翻转还是改变结果res的加入顺序
然后把更新辅助结点p的左右顺序换一下即可
更多相关文章
- 每天一算:二叉树的中序遍历
- 二叉树及其四大遍历
- PHP简短而安全的数组遍历
- 为什么推荐使用for-each而不是for循环遍历元素?
- jQuery遍历祖先元素:parentsUntil
- jQuery在点击按钮上迭代/循环遍历数据表
- 用replaceWith()对DOM结点操作时应注意的问题
- jQuery遍历----------(遍历、祖先、后代、同胞、过滤)
- jQuery遍历Table tr td td中包含标签