层序遍历总结「建议收藏」

层序遍历总结「建议收藏」以LeetCode102作为例子:题目描述思路描述层序遍历需要用到的数据结构是队列。需要考虑的问题是:如何标识当前节点的层数。有以下三种方法:方法1将每个节点表示为一个二元组(node,level),这种方法效率太低,不考虑。感兴趣可以参考方法2遍历完一层节点后,在队列中插入一个标记节点NULL,这个标记节点没有具体意义,只是标识某一层已经遍历结束。这种方法的缺点在于,假如想要在层序遍历过程中,有元素为NULL,那么标记节点就会出现混淆。这种方法的代码我经常用,如下:c

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

以 LeetCode102 作为例子:

题目描述

在这里插入图片描述

思路描述

层序遍历需要用到的数据结构是队列。需要考虑的问题是:如何标识当前节点的层数。
有以下三种方法:

方法 1

将每个节点表示为一个二元组 (node, level),这种方法效率太低,不考虑。感兴趣可以参考

方法 2

遍历完一层节点后,在队列中插入一个标记节点NULL,这个标记节点没有具体意义,只是标识某一层已经遍历结束。
这种方法的缺点在于,假如想要在层序遍历过程中,有元素为 NULL,那么标记节点就会出现混淆。
这种方法的代码我经常用,如下:

class Solution { 
   
    public List<List<Integer>> levelOrder(TreeNode root) { 
   
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(null);
        List<Integer> layer = new ArrayList<>();
        while (!queue.isEmpty()) { 
   
            if (queue.peek() == null) { 
   
                result.add(layer);
                queue.poll();
                if (queue.isEmpty()) break;
                queue.offer(null);
                layer = new ArrayList<>();
                continue;
            }
            TreeNode poll = queue.poll();
            layer.add(poll.val);
            if (poll.left != null) queue.offer(poll.left);
            if (poll.right != null) queue.offer(poll.right);
        }

        return result;
    }
}

Jetbrains全家桶1年46,售后保障稳定

方法 3

方法 3 是按层进行操作队列,每次循环不是取出一个节点,而是取出一整层节点。

我们可以用一种巧妙的方法修改 BFS:

  1. 首先根元素入队
  2. 当队列不为空的时候
    1. 求当前队列的长度 s_is
    2. 依次从队列中取 s_is 个元素进行拓展,然后进入下一次迭代

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

代码如下:

class Solution { 
   
    public List<List<Integer>> levelOrder(TreeNode root) { 
   
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) { 
   
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) { 
   
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) { 
   
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) { 
   
                    queue.offer(node.left);
                }
                if (node.right != null) { 
   
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/231285.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • ES数据库操作入门总结「建议收藏」

    ES数据库操作入门总结「建议收藏」elasticsearch总的来说应该算是一个搜索引擎,公司使用一般是作为日志结果查询。json文档格式,倒排索引的快速以及分布式的特性,使得es可以在大量数据中快速查询到结果。windows安装和配置可参考官方网址。https://www.elastic.co/guide/en/elasticsearch/reference/current/zip-windows.html倒排查询可参考这个知乎回答https://zhuanlan.zhihu.com/p/62892586可以使用浏览器的U

  • 什么是Java虚拟机_Java SDK

    什么是Java虚拟机_Java SDKJAVASDK就是JDK,JDK是整个Java的核心,包括了Java运行环境(JavaRuntimeEnvirnment),一堆Java工具和Java基础的类库(rt.jar)。不论什么Java应用服务器实质都是内置了某个版本的JDK。最主流的JDK是Sun公司发布的JDK,除了Sun之外,还有很多公司和组织都开发了自己的JDK,例如IBM公司开发的JDK,BEA公司的Jrocket,还有GN…

  • Ubuntu系统的基础操作–入门

    Ubuntu系统的基础操作–入门

  • 音频功放的种类和基本原理

    音频功放的种类和基本原理音频功放的种类和基本原理作者:AirCity2019.12.2Aircity007@sina.com本文所有权归作者Aircity所有1 简介功率放大器简称功放,它是将小信号放大,这个放大包括电压和电流,用更大的功率推动音响放声。在技术发展过程中,产生了不同类型的功放种类,按照功率管的导电方式,可以分为甲类功放(又称A类)、乙类功放(又称B类)、甲乙类功放(又称AB类)和丁类功放功…

  • 浏览器被hao.360.cn劫持怎么办

    浏览器被hao.360.cn劫持怎么办特么的现在互联网太没节操了,一大早发现我的浏览器被hao.360.cn劫持了,弄了好久都没弄好,后来一想可能是因为qvod的原因,这可是哥当年看片的神器啊……废话不说:1,进入:C:\ProgramData\QvodPlayer\QvodWebBase2,点开1.0.0.53(或者其它)文件夹3,直接删除里面的文件是删除不了的。更改QvodWebBase64.dll后缀名为QvodWebB…

  • django模型数据类型_多属性决策模型

    django模型数据类型_多属性决策模型模型中常用字段字段说明AutoField一般不需要使用这个类型,自增长类型,数据表的字段类型为整数,长度为11位BigAutoField自增长类型,数据表的字段类型为bigint,长度为2

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号