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

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

【题目】

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

【难度】

解答

没看过前序遍历和中序遍历的或许可以先看下:

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

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

二叉树的后序遍历顺序是左-右-根。我们可以采用一个栈来辅助,不过它和前序遍历以及中序遍历还是有点区别的,我们把后序遍历的结果放到一个 LinkedList 容器中作为返回值,具体步骤如下:

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

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

注意,之前的前序遍历和中序遍历,我们都是用 ArrayList 容器,并且是把节点插入到容器的尾部,这就是后序遍历的不同点。

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

代码如下:

    // 后序遍历
    public List<Integer> postOderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();// 注意,采用链表
        Stack<TreeNode> stack = new Stack<>();
        if(root == null)
            return res;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.pop();
            // 注意,是放在第一个位置
            res.addFirst(tmp.val);
            if(tmp.left != null)
                stack.push(tmp.left);
            if(tmp.right != null)
                stack.push(tmp.right);

        }
        return res;
    }

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

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

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

    帅地
  • 【二叉树打卡2】从上往下打印二叉树

    这个像相当于二叉树四种遍历中的层序遍历了,其思想是采用广度优先遍历,借助一个辅助队列,步骤如下:

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

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

    帅地
  • 如何根据二叉树的两种遍历方式重建二叉树(理论篇)

    我们知道,二叉树有三种不同的遍历方式:先序遍历,中序遍历和后序遍历。这三种遍历方式本质上是根据根节点的位置来命名的。根节点在前面,就是先序遍历;根节点在中间,就...

    青南
  • 5.2二叉搜索树遍历(前序、中序、后序、层次、广度优先遍历)

    前言:在上一节中,我们对树及其相关知识做了了解,对二叉搜索树做了基本的实现,下面我们继续完善我们的二叉搜索树。

    wfaceboss
  • 图的深度遍历和广度遍历

    图的深度遍历和广度遍历都不算很难像极了二叉树的前序遍历和层序遍历,如下面的图,可以用右边的邻接矩阵进行表示,假设以顶点0开始对整幅图进行遍历的话,两种遍历方式的...

    233333
  • 遍历

    前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

    Centy Zhao
  • 二叉树---(3)前序遍历,中序遍历,后序遍历

            很多朋友在刚开始接触二叉树时,对前序遍历,中序遍历,后序遍历这三个遍历方式不太了解,很多博客中,上来就是实现方式,并没有清晰的阐述这三种遍历的步...

    IT云清
  • 【图解数据结构】 一组动画彻底理解二叉树遍历

    定义:二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

    五分钟学算法

扫码关注云+社区

领取腾讯云代金券