首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【二叉树打卡5】二叉树的后序遍历(非递归版)

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

作者头像
帅地
发布2019-06-06 15:33:31
6450
发布2019-06-06 15:33:31
举报
文章被收录于专栏:苦逼的码农苦逼的码农

【题目】

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

【难度】

解答

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

【二叉树打卡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;
    }
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-04-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 帅地玩编程 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 【题目】
  • 【难度】
  • 解答
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档