算法通关村第五关-二叉树遍历(层数优先)之经典问题:简单的层序遍历、层序遍历分层、自底向上的层序遍历

news/2024/12/22 0:49:04/

基础知识(青铜挑战)

  • 了解二叉树的基础知识

实战训练(白银挑战)

简单的层序遍历
  • 基本的层序遍历思路很清晰:

    • 给你一个二叉树根节点,你需要创建一个队列 queue 来遍历节点,一个链表 list 来存储节点的数据域,即值

    • 首先将根节点入队

    • 队列 queue 出队,将该节点值存入 list,再依次将左右孩子节点入队

    • 重复以上操作,每个节点出对后,都存储该节点值到 list 中,再依次将左右孩子节点入队,直到队列 queue为空

    • 这样得到的数据链表 list 就是按层序遍历的顺序得到的

  • 具体代码如下:(2023/09/09午)
public static List<Integer> simpleLevelOrder(TreeNode root) {if (root == null) {return new ArrayList<Integer>();}
​List<Integer> res = new ArrayList<Integer>();LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//将根节点放入队列中,然后不断遍历队列queue.add(root);//有多少元素执行多少次while (queue.size() > 0) {//获取当前队列的长度,这个长度相当于 当前这一层的节点个数TreeNode t = queue.remove();res.add(t.val);if (t.left != null) {queue.add(t.left);}if (t.right != null) {queue.add(t.right);}}return res;}
层序遍历分层
  • 层序遍历我们做到了,这里添加一个要求:对层序遍历的节点值分层处理,即二叉树每层的节点值分别存放进一个链表 list 中

  • 这个代码怎么写呢?很简单的,按这个思路走:

    • 我们之前层序遍历时,每出队一个节点,都把其值存入 list 链表中,然后入队其孩子节点

    • 在开始出队某一层的节点时,此时队列的节点数,就是二叉树这一层的节点数

    • 那我们根据可以某时刻队列容量来遍历队列,将这层的节点全部出队,并且把节点值存入该层独有的 list 中

    • 当然了,每个节点出队后,要将自己的孩子节点依次入队

    • 这样,当队列为空时,我们得到了各层的节点链表 list,返回一个包含各层 list 的 list 即可

  • 具体代码如下:(2023/09/09晚)
  public static List<List<Integer>> level102Order(TreeNode root) {if (root == null) {return new ArrayList<List<Integer>>();}
​List<List<Integer>> res = new ArrayList<List<Integer>>();LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//将根节点放入队列中,然后不断遍历队列queue.add(root);while (queue.size() > 0) {//获取当前队列的长度,这个长度相当于 当前这一层的节点个数int size = queue.size();ArrayList<Integer> tmp = new ArrayList<Integer>();//将队列中的元素都拿出来(也就是获取这一层的节点),放到临时list中//如果节点的左/右子树不为空,也放入队列中for (int i = 0; i < size; ++i) {TreeNode t = queue.remove();tmp.add(t.val);if (t.left != null) {queue.add(t.left);}if (t.right != null) {queue.add(t.right);}}//将临时list加入最终返回结果中res.add(tmp);}return res;}
自底向上的层序遍历
  • 在前面学习的基础上,实现这个要求就很简单了

  • 在拿到各层节点值的 list 后,按头插的方式,插入链表 list 中,就实现了自底向上的层序遍历了(2023/09/09晚)
  • 具体代码如下:
  
public static List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();if (root == null) {return levelOrder;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<Integer>();int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();level.add(node.val);TreeNode left = node.left, right = node.right;if (left != null) {queue.offer(left);}if (right != null) {queue.offer(right);}}levelOrder.add(0, level);//栈}return levelOrder;}


http://www.ppmy.cn/news/1134972.html

相关文章

最短路径专题3 最短距离-多边权

题目&#xff1a; 样例&#xff1a; 输入 4 5 0 2 0 1 2 1 0 2 5 1 0 3 1 2 1 2 1 6 3 2 2 3 输出 3 5 思路&#xff1a; 根据题目意思&#xff0c;其实还是Dijkstra 的题目&#xff0c;不同的是&#xff0c;多了一个最少花费边权的这个点&#xff0c;多添加一个spend数组&am…

Greenplum7一键安装

2023年9月底&#xff0c;Greenplum 发布了7.0.0版本&#xff0c;并于2023年10月03日开放了安装部署说明文档&#xff0c;现在快速尝鲜版的docker一键部署方式如下&#xff1a; mkdir /data/gpdb docker run -d --name greenplum -p 15432:5432 -v /data/gpdb:/data inrgihc/g…

【Spring MVC】MVC原理:DispatcherServlet的初始化,初始化好等于MVC准备好

文章目录 1. EnableWebMVC 开启 MVC 功能2. 初始化自定义的 MVC 组件2.1. 过程2.2. 如何分析复杂的 Spring 组件注册 3. 容器启动后会初始化 DispatcherServlet4. DispatcherServlet 初始化过程总结 把DispatcherServlet 准备好意味着服务器已经可以处理请求了&#xff0c;那么…

基于微信小程序的明星应援小程序设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言系统主要功能&#xff1a;具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计…

python print格式

例子 >>> sid 10>>> print(%s的学号为%.5d %(name,sid))lily的学号为00010>>> sid 1>>> print(%s的学号为%.5d %(name,sid))lily的学号为00001%s:打印字符串 %d:打印整数 %f:打印浮点数 %2s:字符串长度为2&#xff0c;当原字符串长度…

Python之函数、模块、包库

函数、模块、包库基础概念和作用 A、函数 减少代码重复 将复杂问题代码分解成简单模块 提高代码可读性 复用老代码 """ 函数 """# 定义一个函数 def my_fuvtion():# 函数执行部分print(这是一个函数)# 定义带有参数的函数 def say_hello(n…

Linux高性能服务器编程 学习笔记 第九章 IO复用

IO复用使程序能同时监听多个文件描述符&#xff0c;这可以提高程序的性能&#xff0c;通常网络程序在以下情况需要使用IO复用&#xff1a; 1.客户端进程需要同时处理多个socket。 2.客户端进程需要同时处理用户输入和网络连接。 3.TCP服务器要同时处理监听socket和连接socket…

Linux环境下gdb调试方法与演示

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【Linux专栏】&#x1f388; 本专栏旨在分享学习Linux的一点学习心得&#xff0c;欢迎大家在评论区讨论&#x1f48c; 演示环境&#xff1…