专栏首页五分钟学算法每天一算:Binary Tree Preorder Traversal

每天一算:Binary Tree Preorder Traversal

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

题目

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

解题思路

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

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

  • 把根节点push到栈中
  • 循环检测栈是否为空,若不空,则取出栈顶元素,保存其值
  • 看其右子节点是否存在,若存在则push到栈中
  • 看其左子节点,若存在,则push到栈中。

动画演示

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

参考代码

补充

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

  • 辅助结点p初始化为根结点,while循环的条件是栈不为空或者辅助结点p不为空
  • 在循环中首先判断如果辅助结点p存在,那么先将p加入栈中,然后将p的结点值加入结果res中,此时p指向其左子结点
  • 否则如果p不存在的话,表明没有左子结点,我们取出栈顶结点,将p指向栈顶结点的右子结点

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

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

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

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

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

    五分钟学算法
  • 傻瓜都能看懂,30张图彻底理解红黑树!

    当在 10 亿数据中只需要进行十几次比较就能查找到目标时,不禁感叹编程之魅力!人类之伟大呀!

    Rocky0429
  • 数据结构 | 每日一练(39)

    ——老子

    闫小林
  • 前端学习数据结构与算法系列(四):哈希、堆和二叉查找树

    当元素进行 mod 运算后,可能会与其他元素的 mod 值一样,此时数组中已经有其他元素占了这个下标位置,这种存储位置重复了的情况便叫做 冲突,我们来看个例子:

    一只图雀
  • 数据结构学习笔记——树

    1.定义 树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1...

    枉凝眉
  • 什么是红黑树?

    当在10亿数据中只需要进行10几次比较就能查找到目标时,不禁感叹编程之魅力!人类之伟大呀! —— 学红黑树有感。

    小东啊
  • 这 30 张图带你读懂红黑树

    本文将通过图文的方式讲解红黑树的知识点,并且不会涉及到任何代码,相信我,在懂得红黑树实现原理前,看代码会一头雾水的,当原理懂了,代码也就按部就班写而已,没任何难...

    帅地
  • Python数据结构__树

        有且只有一个特殊元素根,剩余元素都可以划分为m个不相交的集合T1、T2、T3...Tm,

    py3study

扫码关注云+社区

领取腾讯云代金券