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

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

前言

昨天把二叉树的先序遍历和中序遍历的题目给弄错了,今天重新补发下。

【题目】

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

【难度】

解答

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

1、把二叉树的根节点 root 放进栈。

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

3、一直重复步骤 2 ,直到栈为空,此时遍历结束,代码如下:

代码如下:

    // 迭代版
    static List<Integer> preOderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null)
            return result;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.pop();
            result.add(tmp.val);
            if(tmp.right != null)
                stack.push(tmp.right);
            if(tmp.left != null)
                stack.push(tmp.right);
        }
        return result;
    }

本文分享自微信公众号 - 苦逼的码农(di201805)

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Caffe与NVIDIA Docker不兼容的问题

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • c++11模板:容器(map,set,list,vector)中元素类型转换

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • Docker理论与实践(四)

    解析:docker run命令,-i是交互模式,-t是提供一个伪终端tty,--rm是在容器退出后自动移除容器。

    Tyan
  • 多个 VUE 前端工程部署设置、nginx 代理配置

    版权声明:这可是本菇凉辛辛苦苦原创的,转载请一定带上我家地址,不要忘记了哈 . https://b...

    微风-- 轻许--
  • Docker/K8s 解决容器内时区不一致方案

    本次演示环境,我是在虚拟机上安装 Linux 系统来执行操作,通过虚拟机完成 Kubernetes 集群的搭建,以下是安装的软件及版本:

    哎_小羊
  • docker:利用maven镜像启动服务的一个示例

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • docker:mysql启动时自动执行初始建表脚本

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • C++11:基于std::queue和std::mutex构建一个线程安全的队列

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • C++ 输入ctrl+z 不能再使用cin的问题

    问题介绍: 程序步骤是开始往容器里面写数据,以Ctrl+Z来终止输入流,然后需要输入一个数据,来判断容器中是否有这个数据。

    zy010101
  • 使用Docker搭建Anaconda Python3.6的练习环境

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan

扫码关注云+社区

领取腾讯云代金券