专栏首页苦逼的码农【二叉树打卡4】二叉树的中序遍历(非递归版)

【二叉树打卡4】二叉树的中序遍历(非递归版)

【题目】

按照二叉树的中序遍历打印二叉树,并且不能使用递归。

【难度】

解答

二叉树的中序遍历顺序是左-根-右。我们可以采用一个栈来辅助,我们把中序遍历的结果放到一个 ArrayList 容器中作为返回值,具体步骤如下:

1、进入 while 循环,接着把根节点及其所有左子节点放入栈中。

2、从栈中取出一个节点,把该节点放入容器的尾部;如果该节点的右子节点不为空,则把右子节点及其右子节点的所有左子节点放入队列。

3、一直重复步骤 2 ,直到栈为空并且当前节点也为空则退出循环。

可能看解释反而有点乱,直接看代码吧,配合代码就容易懂了。

代码如下:

   // 中序遍历
    public List<Integer> inOderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }

本文分享自微信公众号 - 苦逼的码农(di201805),作者:帅地

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

原始发表时间:2019-04-03

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 三分钟基础:什么是 2-3-4 树

    三分钟基础知识:什么是 2-3 树?。本篇文章将在 2-3 树的基础上更进一步,介绍比 2-3 树更为复杂的数据结构 2-3-4树 。之所以介绍 2-3-4 树...

    帅地
  • 三分钟基础知识:什么是 2-3 树?

    前面讲到了二叉搜索树 (BST) 和二叉平衡树 (AVL) :【漫画】以后在有面试官问你AVL树,你就把这篇文章扔给他。

    帅地
  • 详解算法之重建二叉树

    从今天开始,公众号陆陆续续开始插写用动画形式展现算法题,如剑指offer、Leedcode里经典面试题型,同时也会更新数据结构与算法基础、网络原理等知识。

    帅地
  • 2020-08-30:裸写算法:二叉树两个节点的最近公共祖先。

    时间复杂度 O(N) : 其中 N 为二叉树节点数;最差情况下,需要递归遍历树的所有节点。

    福大大架构师每日一题
  • PHP数据结构(十六) ——B树

    PHP数据结构(十六)——B树 (原创内容,转载请注明来源,谢谢) 一、概述 B树在很多地方被称为“B-树”,因为B树的原英文名称为B-tre...

    用户1327360
  • PriorityQueue 源码分析

    tomas家的小拨浪鼓
  • 数据“厨师”ETL竞赛:今天的数据能做些什么?

    它们是一个烹饪比赛的电视系列节目,享有盛名的厨师们撸起袖子,争相做出完美的菜肴。基于一个设定的主题,结合厨师们的经验,创造力和想象力,将可能有问题的食材转化为最...

    用户2176511
  • Selenium系列(十三) - 自动化必备知识之Xpath的详细使用

    https://www.cnblogs.com/poloyy/category/1680176.html

    小菠萝测试笔记
  • 斯坦福教授ICLR演讲:图网络最新进展GraphRNN和GCPN(附PPT下载)

    此外,在 ICLR 受邀演讲上,Jure Leskovec 教授还就图深度生成模型做了演讲。在这次演讲中,Jure 阐述了图生成模型的方法和应用,并详细介绍了他...

    新智元
  • 苹果审核被拒 2.3.10

    GuangdongQi

扫码关注云+社区

领取腾讯云代金券