多叉树题目:N 叉树的层序遍历

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:N 叉树的层序遍历

出处:429. N 叉树的层序遍历

难度

4 级

题目描述

要求

给定一个 N 叉树的根结点 root \texttt{root} root,返回其结点值的层序遍历。

N 叉树在输入中按层序遍历序列化表示,每组子结点由空值 null \texttt{null} null 分隔(请参见示例)。

示例

示例 1:

示例 1

输入: root   =   [1,null,3,2,4,null,5,6] \texttt{root = [1,null,3,2,4,null,5,6]} root = [1,null,3,2,4,null,5,6]
输出: [[1],[3,2,4],[5,6]] \texttt{[[1],[3,2,4],[5,6]]} [[1],[3,2,4],[5,6]]

示例 2:

示例 2

输入: root   =   [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] \texttt{root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]} root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]] \texttt{[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]} [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

数据范围

  • 树中结点数目在范围 [0,   10 4 ] \texttt{[0, 10}^\texttt{4}\texttt{]} [0, 104]
  • N 叉树的高度小于或等于 1000 \texttt{1000} 1000

解法

思路和算法

层序遍历的方法为从根结点开始依次遍历每一层的结点,由于每一层与根结点的距离依次递增,因此可以使用广度优先搜索实现层序遍历。

广度优先搜索需要使用队列存储待访问的结点,初始时将根结点入队列。每次将一个结点出队列,然后将该结点的子结点入队列,直到队列为空时遍历结束。

由于这道题需要将结点值按照不同层分组,因此需要区分不同结点所在的层,确保每一轮访问的结点为同一层的全部结点。

初始时,队列内只有根结点,是同一层的全部结点。每一轮访问结点之前需要首先得到队列内的元素个数,此时队列内的元素为同一层的全部结点,然后访问这些结点,并将这些结点的子结点入队列。一轮访问结束之后,当前层的全部结点都已经出队列并被访问,此时队列内的元素为下一层的全部结点,下一轮访问时即可访问下一层的全部结点。使用上述做法,可以确保每一轮访问的结点为同一层的全部结点。

对于每一层维护一个结点值序列。遍历完每一层结点之后,将该层结点值序列添加到层序遍历序列中。

代码

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> levelOrderTraversal = new ArrayList<List<Integer>>();
        if (root == null) {
            return levelOrderTraversal;
        }
        Queue<Node> queue = new ArrayDeque<Node>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> levelValues = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                List<Node> children = node.children;
                levelValues.add(node.val);
                for (Node child : children) {
                    queue.offer(child);
                }
            }
            levelOrderTraversal.add(levelValues);
        }
        return levelOrderTraversal;
    }
}

复杂度分析

  • 时间复杂度: O ( m ) O(m) O(m),其中 m m m 是二叉树的结点数。每个结点都被访问一次。

  • 空间复杂度: O ( m ) O(m) O(m),其中 m m m 是二叉树的结点数。空间复杂度主要是队列空间,队列内元素个数不超过 m m m

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515860.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

架构之道:架构、结构、中间件、安全性

对本篇文章中有些此不是很理解的&#xff0c;可以看之前讲解的后端通用技术大全&#xff1a;后端技术大全-CSDN博客 一起食用&#xff0c;效果更加。 一、架构到底是什么 关于架构这个概念很难给出一个明确的定义&#xff0c;也没有一个标准的定义。 硬是要给一个概述&#…

社交媒体市场:揭示Facebook的商业模式

在数字化时代&#xff0c;社交媒体已经成为人们生活中不可或缺的一部分。Facebook作为全球最大的社交媒体平台之一&#xff0c;其商业模式的运作方式对于了解社交媒体市场的发展趋势和影响力至关重要。本文将深入探讨Facebook的商业模式&#xff0c;剖析其运作机制&#xff0c;…

ChatGPT 之百万富翁

原文&#xff1a;The ChatGPT Millionaire 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 介绍 当我写下这些文字时&#xff0c;ChatGPT 已经成为有史以来增长最快的技术平台 - 仅用 5 天就达到了一百万用户。相比之下&#xff0c;Netflix 用了 3 年&#xff0c;Twit…

查询SQL server数据库在后台执行过的语句

查询SQL server数据库在后台执行过的语句 SELECT TOP 30000total_worker_time/1000 AS [总消耗CPU 时间(ms)],execution_count [运行次数],qs.total_worker_time/qs.execution_count/1000 AS [平均消耗CPU 时间(ms)],last_execution_time AS [最后一次执行时间],min_worker_ti…

机器狗首次阵亡!美国警方披露详情

ChatGPT狂飙160天&#xff0c;世界已经不是之前的样子。 新建了免费的人工智能中文站https://ai.weoknow.com 新建了收费的人工智能中文站https://ai.hzytsoft.cn/ 更多资源欢迎关注 那天&#xff0c;唯一的伤亡者是我们的机器狗。 美国警察最新公布一则案件&#xff1a;波士顿…

Spring API 接口和自定义类来实现AOP(Spring学习笔记十)

1、什么是AOP 全称是 Aspect Oriented Programming 即&#xff1a;面向切面编程。是OOP&#xff08;面向对象编程&#xff09;的延续&#xff0c;也是Spring框架中的一个重要内容&#xff0c;是函数式编程的一种衍生泛型。简单的说他就是把我们程序重复的代码抽取出来&#xf…

【C++】引用与指针

​​ &#x1f331;博客主页&#xff1a;青竹雾色间. &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注 ✨人生如寄&#xff0c;多忧何为 ✨ 目录标题 前言一.引用&#xff08;Reference&#xff09;二.指针&#xff08;Pointer&#xff09;三. 比较与总结 前…

随机生成Long全范围数

随机生成Long全范围数 前言实现思路主要代码分区随机生成过程案例&#xff1a;随机生成100个数 朴素的比较总结 前言 使用自带的Random.nextLong()函数生成Long型的长整数&#xff0c;范围比较小&#xff0c;如下图。100个随机数没看见10以内的数字。所以考虑实现随机化生成大…

新质生产力丨zData X 数据库一体机助力财政一体化平台全面升级

在数字化转型的大潮中&#xff0c;某财政局积极响应国家财政管理现代化的战略部署&#xff0c;启动了财政一体化平台升级改造工程。该项目旨在将财政局内部各部门及其各自独立的业务系统进行全面整合&#xff0c;构建起一个集约化的财政管理平台&#xff0c;力求通过技术创新推…

【剑指offr--C/C++】JZ31 栈的压入、弹出序列

一、题目 二、思路及代码 借助一个辅助栈来模拟入栈过程&#xff0c; ①在入栈之前先判断当前要入栈的元素是否与出栈数组当前元素相同&#xff0c; ② 如果不相同就入栈&#xff1b; ③如果相同就不用入栈了&#xff08;不入栈出栈&#xff09;&#xff0c;然后再依次取出栈的…

Redis中的复制功能(五)

心跳检测 概述 在命令传播阶段&#xff0c;从服务器默认会以每秒一次的频率&#xff0c;向主服务器发送命令: REPLCONF ACK < replication_offset >其中replication_offset是从服务器当前的复制偏移量。 发送REPLCONF ACK命令对于主从服务器有三个作用: 1.检测主从服…

python学习23:python中的列表(list)中的常用方法

列表(list)中的常用方法 1.列表中常用的方法主要有如下的方法&#xff1a; 2.代码演示主要常用的方法 查找某元素在列表内的下标索引&#xff1a;list.index(元素&#xff09; start_list [coco, xuanxuan, taotao] # 1.1 查找某元素在列表内的下标索引 index start_list…

Arcgis研究区图经纬度(南北)切换为英文字体(SN)

只在做英文论文研究区图的时候用&#xff0c;平常为了方便还是切换为中文

BigInteger 大整数 比较大小

一、以整数型礼品交易为例子 int userSend Integer.valueOf(id);int amount Integer.valueOf(amountStr);int userAccept Integer.valueOf(userIdAccept);GiftService giftService new GiftService();boolean carry1 giftService.isHavePropertyByUserIdByGiftId(userSend…

C++实现vector

目录 前言 1.成员变量 2.成员函数 2.1构造函数 2.2析构函数 2.3begin,end 2.4获取size和capacity 2.5函数重载【】 2.6扩容reserve 2.7resize 2.8insert 2.9删除 2.10尾插、尾删 3.0拷贝构造函数 3.1赋值运算符重载 前言 自主实现C中vector大部分的功能可以使我们更好的理解并使…

第二十二章 Maven

一、Maven 1. Maven 简介 Maven 是一个项目管理工具&#xff0c;可以对 Java 项目进行自动化的构建和依赖管理。Maven 在美国是一个口语化的词语&#xff0c;代表专家、内行的意思&#xff0c;约等于北京话中的老炮儿。有老炮儿在身边&#xff0c;项目经理可谓得心应手。 项…

Redis的5大常见数据类型的用法

上一篇文章我们讲了Redis的10大应用场景&#xff0c;这一篇文章就针对Redis的常用数据结构进行一个说明&#xff0c;通过示例的形式演示每一种数据结构如何使用。 当涉及Redis的数据操作时&#xff0c;不同数据类型对应的不同数据结构&#xff0c;如下就对5大常用的数据类型进行…

[每周一更]-第92期:Go项目中的限流算法

这周五在清明假期内&#xff0c;提前更新文章 很多业务会有限流的场景&#xff0c;比如活动秒杀、社区搜索查询、社区留言功能&#xff1b;保护自身系统和下游系统不被巨型流量冲垮等。 在计算机网络中&#xff0c;限流就是控制网络接口发送或接收请求的速率&#xff0c;它可防…

k8s 部署 canal 集群,RocketMQ 模式

k8s 部署 canal 集群&#xff0c;RocketMQ 模式 k8s 部署 canal 集群&#xff0c;RocketMQ 模式前提MySQLRocketMQ制作 canal-admin、canal-server 镜像 部署 zookeeper部署 canal-admin部署 canal-server测试 k8s 部署 canal 集群&#xff0c;RocketMQ 模式 前提 MySQL 开启…

idea2023.2.1 java项目-web项目创建-servlet类得创建

如何创建Java项目 1.1 方式1&#xff1a; 1.2 方式&#xff1a; 1.3 方式 如何创建web项目 方式 ----- 推荐 如何创建servlet类 复制6 中得代码 给servlet 配置一个路径 启动tomcat 成功了