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

数据结构与算法——N叉树(自学笔记)

本文参考 N 叉树 - LeetBook - 力扣(LeetCode)全球极客挚爱的技术成长平台

遍历

img

  • 前序遍历: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 - 力扣&#xff08;LeetCode&#xff09;全球极客挚爱的技术成长平台 遍历 前序遍历&#xff1a;A->B->C->E->F->D->G后序遍历&#xff1a;B->E->F->C->G->D->A层序遍历&#xff1a;A->B->C->D->…...

【趣味升级版】斗破苍穹修炼文字游戏HTML,CSS,JS

目录 图片展示 开始游戏 手动升级&#xff08;满100%即可升级&#xff09; 升级完成&#xff0c;即可解锁打怪模式 新增功能说明&#xff1a; 如何操作&#xff1a; 完整代码 实现一个简单的斗破苍穹修炼文字游戏&#xff0c;你可以使用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指针的过程&#xff0c;由clk_get、devm_clk_get、clk_get_sys、of_clk_get、of_clk_g…...

安装MySQL 5.7 亲测有效

前言&#xff1a;本文是笔者在安装MySQL5.7时根据另一位博主大大的安装教程基础上做了一些修改而成 首先在这里表示对博主大大的感谢 下面附博主大大地址 下面的步骤言简意赅 跟着做就不会出错 希望各位读者耐下心来 慢慢解决安装中出现的问题~MySQL 5.7 安装教程&#xff08;全…...

《Django 5 By Example》阅读笔记:p455-p492

《Django 5 By Example》学习第 16 天&#xff0c;p455-p492 总结&#xff0c;总计 38 页。 一、技术总结 1.myshop (1)打折功能 使用折扣码实现&#xff0c;但是折扣码是手动生成的&#xff0c;感觉实际业务中应该不是这样的。 (2)推荐功能 使用 Redis 做缓存&#xff0…...

Element-UI 官网的主题切换动画

文章目录 实现圆形扩散过渡动画 实现一下 Element-UI 官网的主题切换动画加粗样式 实现 首先我们起一个 html 文件&#xff0c;写一个按钮&#xff0c;以及简单的背景颜色切换&#xff0c;来模拟主题的切换 想要实现过渡效果&#xff0c;需要先用到一个 JavaScript 的原生方…...

Golang 构建学习

Golang 构建学习 如何搭建Golang开发环境 1. 下载GOlang包 https://golang.google.cn/dl/ 在地址上下载Golang 2. 配置包环境 修改全局环境变量&#xff0c;GOPROXY&#xff0c;GOPATH&#xff0c;GOROOT GOPROXYhttps://goproxy.cn,direct GOROOT"" // go二进…...

VM Virutal Box的Ubuntu虚拟机与windows宿主机之间设置共享文件夹(自动挂载,永久有效)

本文参考如下链接 How to access a shared folder in VirtualBox? - Ask Ubuntu &#xff08;1&#xff09;安装增强功能&#xff08;Guest Additions&#xff09; 首先&#xff0c;在网上下载VBoxGuestAdditions光盘映像文件 下载地址&#xff1a;Index of http://…...

分析 系统滴答时钟(tickClock),设置72MHz系统周期,如何实现1毫秒的系统时间?

一、CubeMX相关配置 1.1 相关引脚配置 1.2 相关时钟数配置 1.3 打开程序源码 二、相关函数分析...

C++优选算法十七 多源BFS

1.单源最短路问题 一个起点一个终点。 定义&#xff1a;在给定加权图中&#xff0c;选择一个顶点作为源点&#xff0c;计算该源点到图中所有其他顶点的最短路径长度。 2.多源最短路问题 定义&#xff1a;多源最短路问题指的是在图中存在多个起点&#xff0c;需要求出从这些…...

Mongodb入门到放弃

Mongodb分片概括 分片在多台服务器上分布数据的方法&#xff0c; Mongodb使用分片来支持具有非常大的数据集和高吞吐量的操作的部署 具有大数据集和高吞吐量应用程序的数据库系统&#xff0c;可以挑战单台服务器的容量。 例如&#xff0c;高查询率可以耗尽服务器的cpu容量&…...

青藤云安全携手财信证券,入选金融科技创新应用优秀案例

11月29日&#xff0c;由中国信息通信研究院主办的第四届“金信通”金融科技创新应用案例评选结果正式发布。财信证券与青藤云安全联合提交的“基于RASP技术的API及数据链路安全治理项目”以其卓越的创新性和先进性&#xff0c;成功入选金融科技创新应用优秀案例。 据悉&#x…...

在CentOS系统中安装工具包的时候报错的解决方法

我刚装了一个新的虚拟机&#xff0c;打算安装一些工具出现了错误信息 执行的命令如下&#xff1a; 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加载失败

一切本来很顺利哒 但是&#xff0c;当我用快捷方式打开时&#xff0c;就出现了这个错误。进入文件路径&#xff0c;是有这个的&#xff1b; 在文件路径直接打开&#xff0c;也会提示错误 原因竟然是我改了个名字&#xff1a; 随便选的文件路径&#xff0c;空的,文件名为Acr…...

14、保存与加载PyTorch训练的模型和超参数

文章目录 1. state_dict2. 模型保存3. check_point4. 详细保存5. Docker6. 机器学习常用库 1. state_dict nn.Module 类是所有神经网络构建的基类&#xff0c;即自己构建一个深度神经网络也是需要继承自nn.Module类才行&#xff0c;并且nn.Module中的state_dict包含神经网络中…...

【前端开发】JS+Vuew3请求列表数据并分页

应用技术&#xff1a;原生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助力电力管廊数据采集,为机器人巡视系统提供精准导航支持

地下电缆是一个城市重要的基础设施&#xff0c;它不仅具有规模大、范围广、空间分布复杂等特点&#xff0c;更重要的是它还承担着信息传输、能源输送等与人们生活息息相关的重要功能&#xff0c;也是一个城市赖以生存和发展的物质基础。 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的上层调用如下&#xff0c;和UdpServer几乎一样&#xff1a; 而在InitServer中&#xff0c;大部分也和UDP那里一样&…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...