数据结构与算法——N叉树(自学笔记)
本文参考 N 叉树 - LeetBook - 力扣(LeetCode)全球极客挚爱的技术成长平台
遍历

- 前序遍历:A->B->C->E->F->D->G
- 后序遍历:B->E->F->C->G->D->A
- 层序遍历:A->B->C->D->E->F->G
(中序遍历只在二叉树有明确定义)
前序遍历
递归
与二叉树一样
import java.util.*;// 定义N叉树节点
class Node{public int val;public List<Node> children; // 使用链表定义子节点public Node(){}public Node(int val){this.val = val;}public Node(int val, List<Node> children){this.val = val;this.children = children;}
}class Solution {public List<Integer> preorder(Node root){List<Integer> res = new ArrayList<Integer>();preorderRecursion(root,res);return res;}public void preorderRecursion(Node root, List<Integer> res){if(root == null){return;}res.add(root.val);for(Node node : root.children){preorderRecursion(node, res);}}
}
- 时间复杂度:O(N),其中 N 是树的节点数。
- 空间复杂度:O(N),即树的高度,最坏情况下递归栈和结果存储的空间需要O(N)的空间。
迭代
与二叉树不一样,很巧妙
class Solution {public List<Integer> preorder(Node root){List<Integer> res = new ArrayList<Integer>();if(root == null){return res;}Deque<Node> stack = new LinkedList<Node>();stack.push(root);while(!stack.isEmpty()){Node node = stack.pop();res.add(node.val);// 逆序入栈for(int i = node.children.size() - 1; i >= 0 ; i--){ stack.push(node.children.get(i)); }}return res;}
}
- 时间复杂度:O(N),其中 N 是树的节点数。
- 空间复杂度:O(N),即树的高度,最坏情况下递归栈和结果存储的空间需要O(N)的空间。
后序遍历
递归
class Solution {public List<Integer> postorder(Node root){List<Integer> res = new ArrayList<Integer>();postorderRecursion(root,res);return res;}public void postorderRecursion(Node root, List<Integer> res){if(root == null){return;}for(Node node : root.children){postorderRecursion(node, res);}res.add(root.val); // 与前序遍历的唯一区别}
}
迭代
与前序遍历相似
class Solution {public List<Integer> postorder(Node root) {// 创建一个列表用来存储后序遍历的结果List<Integer> res = new ArrayList<>();// 如果树为空,直接返回空结果if (root == null) {return res;}// 使用栈进行遍历,栈用来模拟递归Deque<Node> stack = new ArrayDeque<Node>();// 创建一个集合,用来记录已经访问过的节点Set<Node> visited = new HashSet<Node>();// 将根节点推入栈中stack.push(root);// 遍历栈中的节点,直到栈为空while (!stack.isEmpty()) {// 获取栈顶的节点Node node = stack.peek();// 如果当前节点没有子节点(叶子节点),或者子节点已经遍历过if (node.children.size() == 0 || visited.contains(node)) {// 弹出栈顶元素,并将其值加入结果列表stack.pop();res.add(node.val);// 继续下一次循环continue;}// 如果当前节点有未访问的子节点,逆序将子节点压入栈中for (int i = node.children.size() - 1; i >= 0; --i) {stack.push(node.children.get(i));}// 将当前节点标记为已访问visited.add(node);}// 返回存储后序遍历结果的列表return res;}}
- 时间复杂度:O(N),其中 N 是树的节点数。
- 空间复杂度:O(N),即树的高度,最坏情况下递归栈和结果存储的空间需要O(N)的空间。
层序遍历
常规方法
class Solution {public List<List<Integer>> levelOrder (Node root){List<List<Integer>> res = new ArrayList<>();if(root == null){return res;}Queue<Node> queue = new LinkedList<>();Node node = root;queue.offer(node);while(!queue.isEmpty()){List<Integer> level = new ArrayList<>(); // 创建子链表int size = queue.size(); // 计算当前层的大小for(int i = 0; i < size; i++){node = queue.poll(); // 把当前层的节点依次弹出,并加入小链表level.add(node.val);for(Node p : node.children){queue.offer(p); // 把下一层的节点依次加入队列}}res.add(level); // 将小链表加入大链表}return res;}
}
- 时间复杂度:O(N),其中 N 是树的节点数。
- 空间复杂度:O(N),即树的高度,最坏情况下递归栈和结果存储的空间需要O(N)的空间。
递归
N叉树的最大深度
class Solution {public int maxDepth(Node root){if(root == null){return 0;}int maxNmu = 0;List<Node> children = root.children;if (children != null){ // 增强for可以自动处理空集合,但不能处理null,最好添加判断for(Node p : children){maxNmu = Math.max(maxNmu,maxDepth(p)); // 找出最深层}}return maxNmu + 1;}
}
时间复杂度:O(n),其中 n 为 N 叉树节点的个数。每个节点在递归中只被遍历一次。
空间复杂度:O(height),其中 height 表示 N 叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于 N 叉树的高度。
相关文章:
数据结构与算法——N叉树(自学笔记)
本文参考 N 叉树 - LeetBook - 力扣(LeetCode)全球极客挚爱的技术成长平台 遍历 前序遍历:A->B->C->E->F->D->G后序遍历:B->E->F->C->G->D->A层序遍历:A->B->C->D->…...
【趣味升级版】斗破苍穹修炼文字游戏HTML,CSS,JS
目录 图片展示 开始游戏 手动升级(满100%即可升级) 升级完成,即可解锁打怪模式 新增功能说明: 如何操作: 完整代码 实现一个简单的斗破苍穹修炼文字游戏,你可以使用HTML、CSS和JavaScript结合来构建…...
【Oracle】个人收集整理的Oracle常用SQL及命令
【建表】 create table emp( id number(12), name nvarchar2(20), primary key(id) ); 【充值一】 insert into emp select rownum,dbms_random.string(*,dbms_random.value(6,20)) from dual connect by level<101; 【充值二】 begin for i in 1..100 loop inser…...
Linux内核4.14版本——ccf时钟子系统(5)——通用API
1. clk_get 1.1 __of_clk_get_by_name 1.2 clk_get_sys 2. clk_prepare_enable 2.1 clk_prepare 2.2 clk_enable 3. clk_set_rate 1. clk_get clock get是通过clock名称获取struct clk指针的过程,由clk_get、devm_clk_get、clk_get_sys、of_clk_get、of_clk_g…...
安装MySQL 5.7 亲测有效
前言:本文是笔者在安装MySQL5.7时根据另一位博主大大的安装教程基础上做了一些修改而成 首先在这里表示对博主大大的感谢 下面附博主大大地址 下面的步骤言简意赅 跟着做就不会出错 希望各位读者耐下心来 慢慢解决安装中出现的问题~MySQL 5.7 安装教程(全…...
《Django 5 By Example》阅读笔记:p455-p492
《Django 5 By Example》学习第 16 天,p455-p492 总结,总计 38 页。 一、技术总结 1.myshop (1)打折功能 使用折扣码实现,但是折扣码是手动生成的,感觉实际业务中应该不是这样的。 (2)推荐功能 使用 Redis 做缓存࿰…...
Element-UI 官网的主题切换动画
文章目录 实现圆形扩散过渡动画 实现一下 Element-UI 官网的主题切换动画加粗样式 实现 首先我们起一个 html 文件,写一个按钮,以及简单的背景颜色切换,来模拟主题的切换 想要实现过渡效果,需要先用到一个 JavaScript 的原生方…...
Golang 构建学习
Golang 构建学习 如何搭建Golang开发环境 1. 下载GOlang包 https://golang.google.cn/dl/ 在地址上下载Golang 2. 配置包环境 修改全局环境变量,GOPROXY,GOPATH,GOROOT GOPROXYhttps://goproxy.cn,direct GOROOT"" // go二进…...
VM Virutal Box的Ubuntu虚拟机与windows宿主机之间设置共享文件夹(自动挂载,永久有效)
本文参考如下链接 How to access a shared folder in VirtualBox? - Ask Ubuntu (1)安装增强功能(Guest Additions) 首先,在网上下载VBoxGuestAdditions光盘映像文件 下载地址:Index of http://…...
分析 系统滴答时钟(tickClock),设置72MHz系统周期,如何实现1毫秒的系统时间?
一、CubeMX相关配置 1.1 相关引脚配置 1.2 相关时钟数配置 1.3 打开程序源码 二、相关函数分析...
C++优选算法十七 多源BFS
1.单源最短路问题 一个起点一个终点。 定义:在给定加权图中,选择一个顶点作为源点,计算该源点到图中所有其他顶点的最短路径长度。 2.多源最短路问题 定义:多源最短路问题指的是在图中存在多个起点,需要求出从这些…...
Mongodb入门到放弃
Mongodb分片概括 分片在多台服务器上分布数据的方法, Mongodb使用分片来支持具有非常大的数据集和高吞吐量的操作的部署 具有大数据集和高吞吐量应用程序的数据库系统,可以挑战单台服务器的容量。 例如,高查询率可以耗尽服务器的cpu容量&…...
青藤云安全携手财信证券,入选金融科技创新应用优秀案例
11月29日,由中国信息通信研究院主办的第四届“金信通”金融科技创新应用案例评选结果正式发布。财信证券与青藤云安全联合提交的“基于RASP技术的API及数据链路安全治理项目”以其卓越的创新性和先进性,成功入选金融科技创新应用优秀案例。 据悉&#x…...
在CentOS系统中安装工具包的时候报错的解决方法
我刚装了一个新的虚拟机,打算安装一些工具出现了错误信息 执行的命令如下: yum install -y yum-utils device-mapper-persistent-data lvm2错误信息如下 Cannot find a valid baseurl for repo: base/7/x86_64搜索了一下原因有好几种。 一是网络不通…...
cad软件打不开报错cad acbrandres dll加载失败
一切本来很顺利哒 但是,当我用快捷方式打开时,就出现了这个错误。进入文件路径,是有这个的; 在文件路径直接打开,也会提示错误 原因竟然是我改了个名字: 随便选的文件路径,空的,文件名为Acr…...
14、保存与加载PyTorch训练的模型和超参数
文章目录 1. state_dict2. 模型保存3. check_point4. 详细保存5. Docker6. 机器学习常用库 1. state_dict nn.Module 类是所有神经网络构建的基类,即自己构建一个深度神经网络也是需要继承自nn.Module类才行,并且nn.Module中的state_dict包含神经网络中…...
【前端开发】JS+Vuew3请求列表数据并分页
应用技术:原生JavaScript Vue3 $(function () {ini(); });function ini() {const { createApp, ref, onMounted } Vue;createApp({setup() {const data ref({studentList: [],page: 1,pageSize: 10,});const getStudentList async (page, key) > {window.ons…...
Trimble X12助力电力管廊数据采集,为机器人巡视系统提供精准导航支持
地下电缆是一个城市重要的基础设施,它不仅具有规模大、范围广、空间分布复杂等特点,更重要的是它还承担着信息传输、能源输送等与人们生活息息相关的重要功能,也是一个城市赖以生存和发展的物质基础。 01、项目概述 本次项目是对某区域2公里左…...
Docker 清理镜像策略详解
文章目录 前言一、删除 Docker 镜像1. 查看当前镜像2. 删除单个镜像3. 删除多个镜像4. 删除所有未使用的镜像5. 删除悬空的 Docker 镜像6. 根据模式删除镜像7. 删除所有镜像 二、删除 Docker 容器1. 查找容器2. 删除一个或多个特定容器3. 退出时删除容器4. 删除所有已退出的容器…...
【Linux】TCP网络编程
目录 V1_Echo_Server V2_Echo_Server多进程版本 V3_Echo_Server多线程版本 V3-1_多线程远程命令执行 V4_Echo_Server线程池版本 V1_Echo_Server TcpServer的上层调用如下,和UdpServer几乎一样: 而在InitServer中,大部分也和UDP那里一样&…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
