每天一算：Binary Tree Preorder Traversal
16lz
2021-01-22
题目
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解题思路
用栈(Stack)的思路来处理问题。
前序遍历的顺序为根-左-右，具体算法为：
把根节点push到栈中
循环检测栈是否为空，若不空，则取出栈顶元素，保存其值
看其右子节点是否存在，若存在则push到栈中
看其左子节点，若存在，则push到栈中。
动画演示
动画演示GIF加载有点慢，请稍待片刻加载显示^_^
参考代码
补充
下面这种写法使用了一个辅助结点p，这种写法其实可以看作是一个模版，对应的还有中序和后序的模版写法，形式很统一，方便于记忆。后续更新的中序和后序文章中都会补充该写法。思路与代码如下：
辅助结点p初始化为根结点，while循环的条件是栈不为空或者辅助结点p不为空
在循环中首先判断如果辅助结点p存在，那么先将p加入栈中，然后将p的结点值加入结果res中，此时p指向其左子结点
否则如果p不存在的话，表明没有左子结点，我们取出栈顶结点，将p指向栈顶结点的右子结点
更多相关文章
- 详解PHP死循环写法和作用
- PHP让人不知道的匿名函数的几种写法（附代码）
- 学习PHP死循环写法和作用
- 详细解说三种PHP嵌套HTML的写法
- PHP+Swoole的闭包写法
- 单例模式的十种写法，你会几个？
- 单例模式你会几种写法？
- 单例模式的十种写法，你会几个？（修补了几个错误点）
- 单例模式的十种写法，你会几个？（重写版）