专栏首页五分钟学算法每天一算:二叉树的中序遍历

每天一算:二叉树的中序遍历

LeetCode上第94 号问题:二叉树的中序遍历

题目

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

解题思路

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

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

  • 从根节点开始,先将根节点压入栈
  • 然后再将其所有左子结点压入栈,取出栈顶节点,保存节点值
  • 再将当前指针移到其右子节点上,若存在右子节点,则在下次循环时又可将其所有左子结点压入栈中

动画演示

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

参考代码

补充

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

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

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    五分钟学算法
  • 每天一算:Binary Tree Preorder Traversal

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

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

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

    五分钟学算法
  • 数据结构简单要点总结(转)

    栈是只能在一端进行插入和删除的线性表。 (别看只是个定义,非常重要,已经道出了运算方法:只能在一端插入和删除。)

    Locker
  • 图解B+树的插入过程

    B+ 树在现代数据库中很常见,如果我们了解它,在工作中可能对性能优化会有更好的帮助!

    业余草
  • 《大话数据结构》(二)

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

    硬核项目经理
  • 6.3.1 B树及其基本操作

    B树,又称多路平衡查找树,B树中所有节点的孩子结点数的最大值成为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树:

    week
  • 红黑树深入浅出

    先来看下算法导论对R-B Tree的介绍: 红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条...

    bear_fish
  • 【数据结构系列】单链表

    最近也一直在思考该写点什么文章,想了很久,还是决定重新编写一下数据结构的相关内容,关于数据结构的重要性就不用我多说了,之前的文章中我也写过,但实现语言是Java...

    wangweijun
  • 当Kotlin遇见数据结构丨数据结构之树结构概述(含满二叉树、完全二叉树、平衡二叉树、二叉搜索树、红黑树、B-树、B+树、B*树)

    B-tree(多路搜索树,并不是二叉的)是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程,从而加快存取速度。按照翻译,B 通常认...

    码脑

扫码关注云+社区

领取腾讯云代金券