当前位置: 首页 > news >正文

LeetCode题练习与总结:N 叉树的前序遍历--589

一、题目描述

给定一个 n 叉树的根节点  root ,返回 其节点值的 前序遍历 。

n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。


示例 1:

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

示例 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]
输出:[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

提示:

  • 节点总数在范围 [0, 10^4]
  • 0 <= Node.val <= 10^4
  • n 叉树的高度小于或等于 1000

二、解题思路

  1. 理解n叉树的结构:n叉树的每个节点包含一个整数值和一个子节点列表。子节点列表可能为空,也可能包含多个子节点。

  2. 前序遍历的定义:前序遍历是指首先访问根节点,然后按从左到右的顺序遍历每个子节点,并对每个子节点递归地进行前序遍历。

  3. 递归方法:我们使用递归方法来遍历n叉树。递归是一种常用的处理树结构的方法,因为它可以简化代码并自然地处理树中的递归关系。

三、具体代码

import java.util.ArrayList;
import java.util.List;// Solution类的定义
public class Solution {public List<Integer> preorder(Node root) {List<Integer> result = new ArrayList<>();if (root != null) {result.add(root.val); // 访问当前节点for (Node child : root.children) { // 递归访问所有子节点result.addAll(preorder(child));}}return result;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

时间复杂度是指算法执行所需时间的量度,通常用大O符号表示。

对于给定的preorder方法:

  • 访问当前节点:这一步是常数时间操作,记为O(1)。
  • 递归访问子节点:对于每个节点,我们都要递归地访问它的所有子节点。如果树的高度为h,并且每个节点有最多n个子节点,那么在最坏的情况下,每个节点都会被访问一次。

由于我们访问每个节点一次,并且每次访问都涉及到将节点的值添加到结果列表中,这个操作是常数时间的。然而,我们需要对每个节点的所有子节点进行递归调用。因此,时间复杂度取决于树的总节点数。

在n叉树中,如果每个节点都有n个子节点,那么树的总节点数大约是n^h(这里h是树的高度)。然而,在实际情况中,树的形状可能不会如此均匀,所以我们使用平均情况下的节点数来估计时间复杂度。

因此,时间复杂度是O(N),其中N是树中节点的总数。

2. 空间复杂度

空间复杂度是指算法执行过程中所需额外空间的最大量度。

对于给定的preorder方法:

  • 结果列表:这个列表的大小与树中节点的数量成正比,因此它需要O(N)的空间,其中N是树中节点的总数。
  • 递归栈:由于我们使用递归,每次递归调用都会在调用栈上占用一定的空间。在最坏的情况下,递归栈的深度等于树的高度h。因此,递归栈的空间复杂度是O(h)。

综上所述,空间复杂度主要取决于递归栈的深度和结果列表的大小。在大多数情况下,树的高度h远小于节点总数N,所以递归栈的空间复杂度通常可以忽略不计。因此,总的空间复杂度可以认为是O(N)。

五、总结知识点

  • 类定义

    • public class Solution:定义了一个名为Solution的公共类,这意味着它可以从其他类中被访问。
  • 方法定义

    • public List<Integer> preorder(Node root):定义了一个公共方法preorder,它接受一个Node类型的参数root,并返回一个List<Integer>类型的对象。
  • 数据结构

    • List<Integer>:使用Java集合框架中的List接口来存储整数类型的元素。
    • ArrayList<Integer>:实现List接口的ArrayList类,用于创建可调整大小的数组。
  • 条件语句

    • if (root != null):这是一个条件判断,用于检查传入的节点是否为null
  • 循环结构

    • for (Node child : root.children):使用增强型for循环来遍历Node对象的children列表。
  • 递归

    • result.addAll(preorder(child)):递归调用preorder方法,并将返回的列表添加到结果列表中。这是前序遍历的核心,递归地访问每个子节点。
  • 方法调用

    • result.add(root.val):调用ArrayListadd方法来添加元素到列表的末尾。
    • result.addAll(...):调用ArrayListaddAll方法来合并两个列表。
  • 返回值

    • return result;:返回包含前序遍历结果的列表。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

相关文章:

LeetCode题练习与总结:N 叉树的前序遍历--589

一、题目描述 给定一个 n 叉树的根节点 root &#xff0c;返回 其节点值的 前序遍历 。 n 叉树 在输入中按层序遍历进行序列化表示&#xff0c;每组子节点由空值 null 分隔&#xff08;请参见示例&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [1,null,3,2,4,nu…...

WebSocket 详解:全双工通信的实现与应用

目录 一、什么是 WebSocket&#xff1f;&#xff08;简介&#xff09; 二、为什么需要 WebSocket&#xff1f; 三、HTTP 与 WebSocket 的区别 WebSocket 的劣势 WebSocket 的常见应用场景 WebSocket 握手过程 WebSocket 事件处理和生命周期 一、什么是 WebSocket&#xf…...

【漫话机器学习系列】064.梯度下降小口诀(Gradient Descent rule of thume)

梯度下降小口诀 为了帮助记忆梯度下降的核心原理和关键注意事项&#xff0c;可以用以下简单口诀来总结&#xff1a; 1. 基本原理 损失递减&#xff0c;梯度为引&#xff1a;目标是让损失函数减少&#xff0c;依靠梯度指引方向。负梯度&#xff0c;反向最短&#xff1a;沿着负…...

Vue 3 中的 TypeScript:接口、自定义类型与泛型

在 Vue 3 中&#xff0c;TypeScript 提供了强大的类型系统&#xff0c;帮助我们更好地管理代码的类型安全。通过使用 接口&#xff08;Interface&#xff09;、自定义类型&#xff08;Type Aliases&#xff09; 和 泛型&#xff08;Generics&#xff09;&#xff0c;我们可以编…...

[SaaS] 内容创意生产平台

1.即梦 2.讯飞绘镜 typemovie 3.Krea.ai 4.Pika 5.runway 6.pixVerse 7....

低代码系统-产品架构案例介绍、明道云(十一)

明道云HAP-超级应用平台(Hyper Application Platform)&#xff0c;其实就是企业级应用平台&#xff0c;跟微搭类似。 通过自设计底层架构&#xff0c;兼容各种平台&#xff0c;使用低代码做到应用搭建、应用运维。 企业级应用平台最大的特点就是隐藏在冰山下的功能很深&#xf…...

2025年1月26日(超声波模块:上拉或下拉电阻)

添加上拉或下拉电阻是在电子电路设计和嵌入式系统编程中常用的一种技术手段&#xff0c;下面为你详细解释其含义、作用和应用场景。 基本概念 在数字电路里&#xff0c;引脚的电平状态通常有高电平&#xff08;逻辑 1&#xff09;和低电平&#xff08;逻辑 0&#xff09;两种…...

【自然语言处理(NLP)】深度循环神经网络(Deep Recurrent Neural Network,DRNN)原理和实现

文章目录 介绍深度循环神经网络&#xff08;DRNN&#xff09;原理和实现结构特点工作原理符号含义公式含义 应用领域优势与挑战DRNN 代码实现 个人主页&#xff1a;道友老李 欢迎加入社区&#xff1a;道友老李的学习社区 介绍 **自然语言处理&#xff08;Natural Language Pr…...

C语言学习阶段性总结(五)---函数

函数构成五要素&#xff1a; 1、返回值类型 2、函数名 3、参数列表&#xff08;输入&#xff09; 4、函数体 &#xff08;算法&#xff09; 5、返回值 &#xff08;输出&#xff09; 返回值类型 函数名 (参数列表) { 函数体&#xff1b; return 返回值&#xff1b; } void 类型…...

C++初阶—string类

第一章&#xff1a;为什么要学习string类 1.1 C语言中的字符串 C语言中&#xff0c;字符串是以\0结尾的一些字符的集合&#xff0c;为了操作方便&#xff0c;C标准库中提供了一些str系列的库函数&#xff0c;但是这些库函数与字符串是分离开的&#xff0c;不太符合OOP的思想&…...

Solon Cloud Gateway 开发:Route 的过滤器与定制

RouteFilterFactory 是专为路由过滤拦截处理设计的接口。对应路由配置 filters 1、内置的路由过滤器 过滤器工厂本置前缀说明与示例AddRequestHeaderFilterFactoryAddRequestHeader添加请求头 (AddRequestHeaderDemo-Ver,1.0)AddResponseHeaderFilterFactoryAddResponseHeade…...

【MySQL】 数据类型

欢迎拜访&#xff1a;雾里看山-CSDN博客 本篇主题&#xff1a;【MySQL】 数据类型 发布时间&#xff1a;2025.1.27 隶属专栏&#xff1a;MySQL 目录 数据类型分类数值类型tinyint类型数值越界测试结果说明 bit类型基本语法使用注意事项 小数类型float语法使用注意事项 decimal语…...

基于vue和elementui的简易课表

本文参考基于vue和elementui的课程表_vue实现类似课程表的周会议列表-CSDN博客&#xff0c;原程序在vue3.5.13版本下不能运行&#xff0c;修改两处&#xff1a; 1&#xff09;slot-cope改为v-slot 2&#xff09;return background-color:rgb(24 144 255 / 80%);color: #fff; …...

vim的多文件操作

[rootxxx ~]# vim aa.txt bb.txt cc.txt #多文件操作 next #下一个文件 prev #上一个文件 first #第一个文件 last #最后一个文件 快捷键: ctrlshift^ #当前和上个之间切换 说明&#xff1a;快捷键ctrlshift^&#xff0c…...

spring spring-boot spring-cloud发布以及适配

https://spring.io/blog/2024/10/01/from-spring-framework-6-2-to-7-0 看了 spring 的官网&#xff0c;提到 2025 年 spring 会跟随 jdk 25 LTS发布后&#xff0c;接着发布 Spring Framework 7.0 GA&#xff0c;与之对应 spring 系列的组件版本情况如下。 Spring Framework版…...

【快速上手】阿里云百炼大模型

为了创建自己的知识库&#xff0c;本文介绍一下阿里云的百炼大模型&#xff0c;方便大家快速上手&#xff01;快速查询自己想要的内容。 一、入口页 阿里云登录 - 欢迎登录阿里云&#xff0c;安全稳定的云计算服务平台 二、大模型的选择 首先前提条件是 1、账号不能欠费 2、需…...

Linux:多线程[2] 线程控制

了解&#xff1a; Linux底层提供创建轻量级进程/进程的接口clone&#xff0c;通过选择是否共享资源创建。 vfork和fork都调用的clone进行实现&#xff0c;vfork和父进程共享地址空间-轻量级进程。 库函数pthread_create调用的也是底层的clone。 POSIX线程库 与线程有关的函数构…...

010 mybatis-PageHelper分页插件

文章目录 添加依赖配置PageHelper项目中使用PageHelper注意事项 PageHelper分页插件介绍 https://github.com/pagehelper/Mybatis-PageHelper/blob/master/wikis/en/HowToUse.md 使用方法 添加依赖 <dependency><groupId>com.github.pagehelper</groupId>&l…...

【huawei】云计算的备份和容灾

目录 1 备份和容灾 2 灾备的作用&#xff1f; ① 备份的作用 ② 容灾的作用 3 灾备的衡量指标 ① 数据恢复时间点&#xff08;RPO&#xff0c;Recoyery Point Objective&#xff09; ② 应用恢复时间&#xff08;RTO&#xff0c;Recoyery Time Objective&#xff09; 4…...

CVE-2023-38831 漏洞复现:win10 压缩包挂马攻击剖析

目录 前言 漏洞介绍 漏洞原理 产生条件 影响范围 防御措施 复现步骤 环境准备 具体操作 前言 在网络安全这片没有硝烟的战场上&#xff0c;新型漏洞如同隐匿的暗箭&#xff0c;时刻威胁着我们的数字生活。其中&#xff0c;CVE - 2023 - 38831 这个关联 Win10 压缩包挂…...

回顾:Maven的环境搭建

1、下载apache-maven-3.6.0 **网址:**http://maven.apache.org 然后解压到指定的文件夹&#xff08;记住文件路径&#xff09; 2、配置Maven环境 复制bin文件夹 的路径D:\JavaTool\apache-maven-3.6.0\bin 环境配置成功 3、检查是否配置成功 winR 输入cmd 命令行输入mvn -v…...

从零到全栈开发

HTML&#xff1a;超文本标记语言 CSS&#xff1a;层叠样式表 HTML可以理解为框架----&#xff08;毛坯房&#xff09; CSS 可以理解为装修----&#xff08;装修&#xff09; 学习工具&#xff1a; Vscode应用----扩展&#xff08;中文&#xff09; AI ----KiMi &#xff0c;豆…...

单片机-STM32 WIFI模块--ESP8266 (十二)

1.WIFI模块--ESP8266 名字由来&#xff1a; Wi-Fi这个术语被人们普遍误以为是指无线保真&#xff08;Wireless Fidelity&#xff09;&#xff0c;并且即便是Wi-Fi联盟本身也经常在新闻稿和文件中使用“Wireless Fidelity”这个词&#xff0c;Wi-Fi还出现在ITAA的一个论文中。…...

两种交换排序算法--冒泡,快速

目录 1.冒泡排序原理 2.快速排序原理 3.冒泡代码实现 4.快速排序代码实现 1.冒泡排序原理 冒泡排序&#xff08;Bubble Sort&#xff09;是一种简单的排序算法&#xff0c;基本思想是通过反复交换相邻的元素&#xff0c;直到整个序列有序。它的名字来源于较大的元素像气泡…...

langchain基础(一)

模型又可分为语言模型&#xff08;擅长文本补全&#xff0c;输入和输出都是字符串&#xff09;和聊天模型&#xff08;擅长对话&#xff0c;输入时消息列表&#xff0c;输出是一个消息&#xff09;两大类。 以调用openai的聊天模型为例&#xff0c;先安装langchain_openai库 1…...

【学术会议征稿】第五届能源、电力与先进热力系统学术会议(EPATS 2025)

能源、电力与先进热力系统设计是指结合物理理论、工程技术和计算机模拟&#xff0c;对能源转换、利用和传输过程进行设计的学科领域。它涵盖了从能源的生产到最终的利用整个流程&#xff0c;旨在提高能源利用效率&#xff0c;减少能源消耗和环境污染。 重要信息 官网&#xf…...

MyBatis框架基础学习及入门案例(2)

目录 一、数据库建表(tb_user)以及添加数据。 &#xff08;1&#xff09;数据库与数据表说明。 &#xff08;2&#xff09;字段与数据说明。 二、创建模块(或工程)、导入对应所需依赖坐标。 三、编写MyBatis核心主配置文件。(解决JDBC中"硬编码"问题) &#xff08;1&…...

Salesforce Too Many Email Invocations: 11

在 Salesforce 中&#xff0c;“Too Many Email Invocations: 11” 错误通常表示您的组织在单个事务中超过了 Apex 电子邮件调用的限制。Salesforce 设置这些限制是为了防止滥用并确保公平使用。以下是解决该问题的方法&#xff1a; 理解限制 Salesforce 允许每个事务中最多进…...

2274. 不含特殊楼层的最大连续楼层数

2274. 不含特殊楼层的最大连续楼层数 题目链接&#xff1a;2274. 不含特殊楼层的最大连续楼层数 代码如下&#xff1a; class Solution { public:int maxConsecutive(int bottom, int top, vector<int>& special) {ranges::sort(special);int res max(special[0] …...

RGB 转HSV空间颜色寻找色块

文章目录 前言一、绿色确定二、红色确定总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 项目需要&#xff1a; 将RGB颜色空间转换为HSV颜色空间以寻找颜色&#xff0c;主要基于以下几个原因&#xff1a; 直观性&#xff1a; HSV颜色空间更符合人类…...

Kafka生产者ACK参数与同步复制

目录 生产者的ACK参数 ack等于0 ack等于1&#xff08;默认&#xff09; ack等于-1或all Kafka的同步复制 使用误区 生产者的ACK参数 Kafka的ack机制可以保证生产者发送的消息被broker接收成功。 Kafka producer有三种ack机制 &#xff0c;分别是 0&#xff0c;1&#xf…...

计算机图形学试题整理(期末复习/闭or开卷/>100道试题/知识点)

1.各种坐标变换&#xff0c;会产生变换前后维度改变的是&#xff08;投影变换&#xff09;。 A&#xff09;建模变换&#xff1b;B&#xff09;观察变换&#xff1b;C&#xff09;投影变换&#xff1b;D&#xff09;视口变换 不同的坐标变换对维度的影响如下&#xff1a; 建模…...

Ubuntu 24.04 安装 NVIDIA Container Toolkit 全指南:让Docker拥抱GPU

Ubuntu 24.04 安装 NVIDIA Container Toolkit 全指南&#xff1a;让Docker拥抱GPU 前言一、环境准备1.1 验证驱动状态 二、安装NVIDIA Container Toolkit2.1 添加官方仓库2.2 执行安装 三、配置Docker运行时3.1 更新Docker配置 四、验证安装结果4.1 运行测试容器 五、实战应用 …...

python3+TensorFlow 2.x(三)手写数字识别

目录 代码实现 模型解析&#xff1a; 1、加载 MNIST 数据集&#xff1a; 2、数据预处理&#xff1a; 3、构建神经网络模型&#xff1a; 4、编译模型&#xff1a; 5、训练模型&#xff1a; 6、评估模型&#xff1a; 7、预测和可视化结果&#xff1a; 输出结果&#xff…...

aws(学习笔记第二十六课) 使用AWS Elastic Beanstalk

aws(学习笔记第二十六课) 使用aws Elastic Beanstalk 学习内容&#xff1a; AWS Elastic Beanstalk整体架构AWS Elastic Beanstalk的hands onAWS Elastic Beanstalk部署node.js程序包练习使用AWS Elastic Beanstalk的ebcli 1. AWS Elastic Beanstalk整体架构 官方的guide AWS…...

GestureDetector组件的功能与用法

文章目录 1 概念介绍2 使用方法3 示例代码 我们在上一章回中介绍了ListView响应事件的内容,本章回中将介绍GestureDetector Widget.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1 概念介绍 我们在这里介绍的GestureDetector是一个事件响应Widget,它可以响应双击事件&…...

【HuggingFace项目】:Open-R1 - DeepSeek-R1 大模型开源复现计划

项目链接&#xff1a;https://github.com/huggingface/open-r1 概述 Open-R1 是由 HuggingFace 发布的一个完全开放的项目&#xff0c;旨在通过三个主要步骤复现 DeepSeek-R1 的完整训练流程。这个项目的目标是让更多人能够理解和使用 DeepSeek-R1 的技术方案&#xff0c;从而…...

K8S中数据存储之配置存储

配置存储 在Kubernetes中&#xff0c;ConfigMap和Secret是两种核心资源&#xff0c;用于存储和管理应用程序的配置数据和敏感信息。理解它们的功能和最佳实践对于提高Kubernetes应用程序的安全性和配置管理的效率至关重要。 ConfigMap ConfigMap是一种API对象&#xff0c;允许…...

群辉折腾日记【连续剧】

安装群辉6.23版本 对比不同的版本以及自己的硬件条件&#xff0c;我选择了6.2.3稳定养老版本&#xff0c;硬件参数可以看之前的文章&#xff1a;pve (群辉、软路由、win/linux)折腾日记 之前年轻气盛喜欢折腾&#xff0c;秉持着一个原则&#xff0c;可以不用&#xff0c;但不能…...

AIGC视频生成模型:慕尼黑大学、NVIDIA等的Video LDMs模型

大家好&#xff0c;这里是好评笔记&#xff0c;公主号&#xff1a;Goodnote&#xff0c;专栏文章私信限时Free。本文详细介绍慕尼黑大学携手 NVIDIA 等共同推出视频生成模型 Video LDMs。NVIDIA 在 AI 领域的卓越成就家喻户晓&#xff0c;而慕尼黑大学同样不容小觑&#xff0c;…...

Hadoop 与 Spark:大数据处理的比较

&#x1f496; 欢迎来到我的博客&#xff01; 非常高兴能在这里与您相遇。在这里&#xff0c;您不仅能获得有趣的技术分享&#xff0c;还能感受到轻松愉快的氛围。无论您是编程新手&#xff0c;还是资深开发者&#xff0c;都能在这里找到属于您的知识宝藏&#xff0c;学习和成长…...

VB6.0 显示越南语字符

近期接到客户咨询&#xff0c;说是VB6.0写软件界面上显示越南语乱码&#xff0c;需要看看怎样解决。 我在自己电脑上也试了下&#xff0c;确实显示越南语结果是乱码。编辑器里乱码&#xff0c;运行起来界面上也是乱码。 经过一天的折腾&#xff0c;算是解决了问题&#xff0c…...

微信小程序中实现进入页面时数字跳动效果(自定义animate-numbers组件)

微信小程序中实现进入页面时数字跳动效果 1. 组件定义,新建animate-numbers组件1.1 index.js1.2 wxml1.3 wxss 2. 使用组件 1. 组件定义,新建animate-numbers组件 1.1 index.js // components/animate-numbers/index.js Component({properties: {number: {type: Number,value…...

网络仿真工具Core环境搭建

目录 安装依赖包 源码下载 Core安装 FAQ 下载源码TLS出错误 问题 解决方案 找不到dbus-launch 问题 解决方案 安装依赖包 调用以下命令安装依赖包 apt-get install -y ca-certificates git sudo wget tzdata libpcap-dev libpcre3-dev \ libprotobuf-dev libxml2-de…...

JavaScript 的 Promise 对象和 Promise.all 方法的使用

JavaScript 中的 Promise 对象 什么是 Promise? Promise 是一种用于处理异步操作的对象。它代表一个尚未完成但预计将来会完成的操作及其结果。 主要特点&#xff1a; 状态: Pending&#xff08;进行中&#xff09;: 初始状态&#xff0c;既未成功&#xff0c;也未失败。Fu…...

农产品价格报告爬虫使用说明

农产品价格报告爬虫使用说明 # ************************************************************************** # * * # * 农产品价格报告爬虫 …...

Java 大视界 -- Java 大数据中的隐私增强技术全景解析(64)

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…...

实战Linux Swap扩展分区

文章目录 定义命令格式案例注释 定义 Swap分区是Linux系统中的一种虚拟内存实现方式&#xff0c;它是磁盘上预留的专用区域。当系统的物理内存不足时&#xff0c;会将部分不活跃的数据从物理内存移动到Swap分区&#xff0c;从而释放更多可用内存空间。 命令格式 关闭Swap分区…...

doris:Parquet导入数据

本文介绍如何在 Doris 中导入 Parquet 格式的数据文件。 支持的导入方式​ 以下导入方式支持 Parquet 格式的数据导入&#xff1a; Stream LoadBroker LoadINSERT INTO FROM S3 TVFINSERT INTO FROM HDFS TVF 使用示例​ 本节展示了不同导入方式下的 Parquet 格式使用方法…...

Synology 群辉NAS安装(6)安装mssql

Synology 群辉NAS安装&#xff08;6&#xff09;安装mssql 写在前面mssql 2019:成功安装说明&#xff0c;这个最终成功了 mssql 2022没有成功1. pull image2.启动mssql docker container 远程连接 写在前面 mssq是一个重要节点。 这是因为我对mysql没有一丝好感。虽然接触了许…...