每天一算:Binary Tree Preorder Traversal

LeetCode上第144 号问题:二叉树的前序遍历

题目

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

示例:

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

输出: [1,2,3]

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

解题思路

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

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

  • 把根节点push到栈中

  • 循环检测栈是否为空,若不空,则取出栈顶元素,保存其值

  • 看其右子节点是否存在,若存在则push到栈中

  • 看其左子节点,若存在,则push到栈中。

动画演示

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

每天一算:Binary Tree Preorder Traversal

参考代码

每天一算:Binary Tree Preorder Traversal


补充

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

  • 辅助结点p初始化为根结点,while循环的条件是栈不为空或者辅助结点p不为空

  • 在循环中首先判断如果辅助结点p存在,那么先将p加入栈中,然后将p的结点值加入结果res中,此时p指向其左子结点

  • 否则如果p不存在的话,表明没有左子结点,我们取出栈顶结点,将p指向栈顶结点的右子结点


每天一算:Binary Tree Preorder Traversal


是一种鼓励 |分享传递友谊

每天一算:Binary Tree Preorder Traversal

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

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

GitHub 哔哩哔哩