层序遍历练习

层次遍历 II

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
在这里插入图片描述

思路

相对于102.二叉树的层序遍历,就是最后把result数组反转一下就可以了。

C++代码:

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}reverse(result.begin(), result.end()); // 在这里反转一下数组即可return result;}
};

右视图

给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
在这里插入图片描述

思路

层序遍历的时候,判断是否遍历到单层的最后面的元素,如果是,就放进result数组中,随后返回result就可以了。

C++代码:

class Solution {
public:vector<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<int> result;while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (i == (size - 1)) result.push_back(node->val); // 将每一层的最后元素放入result数组中if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};

层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
在这里插入图片描述

思路

本题就是层序遍历的时候把一层求个总和再取一个均值。

C++代码:

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<double> result;while (!que.empty()) {int size = que.size();double sum = 0; // 统计每一层的和for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();sum += node->val;if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(sum / size); // 将每一层均值放进结果集}return result;}
};

N叉树的层序遍历

给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。

例如,给定一个 3叉树 :
在这里插入图片描述

思路

这道题依旧是模板题,只不过一个节点有多个孩子了

C++代码:

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {queue<Node*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;for (int i = 0; i < size; i++) {Node* node = que.front();que.pop();vec.push_back(node->val);for (int i = 0; i < node->children.size(); i++) { // 将节点孩子加入队列if (node->children[i]) que.push(node->children[i]);}}result.push_back(vec);}return result;}
};

在每个树行中找最大值

您需要在二叉树的每一行中找到最大的值。

在这里插入图片描述

思路

层序遍历,取每一层的最大值

C++代码:

class Solution {
public:vector<int> largestValues(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<int> result;while (!que.empty()) {int size = que.size();int maxValue = INT_MIN; // 取每一层的最大值for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();maxValue = node->val > maxValue ? node->val : maxValue;if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(maxValue); // 把最大值放进数组}return result;}
};

每个节点的下一个右侧节点指针

给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。
在这里插入图片描述

思路

本题依然是层序遍历,只不过在单层遍历的时候记录一下本层的头部节点,然后在遍历的时候让前一个节点指向本节点就可以了

C++代码:

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();// vector<int> vec;Node* nodePre;Node* node;for (int i = 0; i < size; i++) {if (i == 0) {nodePre = que.front(); // 取出一层的头结点que.pop();node = nodePre;} else {node = que.front();que.pop();nodePre->next = node; // 本层前一个节点next指向本节点nodePre = nodePre->next;}if (node->left) que.push(node->left);if (node->right) que.push(node->right);}nodePre->next = NULL; // 本层最后一个节点指向NULL}return root;}
};

每个节点的下一个右侧节点指针II

思路

这道题目说是二叉树,但116题目说是完整二叉树,其实没有任何差别,一样的代码一样的逻辑一样的味道

C++代码:

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();vector<int> vec;Node* nodePre;Node* node;for (int i = 0; i < size; i++) {if (i == 0) {nodePre = que.front(); // 取出一层的头结点que.pop();node = nodePre;} else {node = que.front();que.pop();nodePre->next = node; // 本层前一个节点next指向本节点nodePre = nodePre->next;}if (node->left) que.push(node->left);if (node->right) que.push(node->right);}nodePre->next = NULL; // 本层最后一个节点指向NULL}return root;}
};

二叉树的最大深度

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],
在这里插入图片描述

思路

使用迭代法的话,使用层序遍历是最为合适的,因为最大的深度就是二叉树的层数,和层序遍历的方式极其吻合。

class Solution {
public:int maxDepth(TreeNode* root) {if (root == NULL) return 0;int depth = 0;queue<TreeNode*> que;que.push(root);while(!que.empty()) {int size = que.size();depth++; // 记录深度for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return depth;}
};

最小深度

思路

需要注意的是,只有当左右孩子都为空的时候,才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

代码如下:(详细注释)

class Solution {
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;int depth = 0;queue<TreeNode*> que;que.push(root);while(!que.empty()) {int size = que.size();depth++; // 记录最小深度for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (node->left) que.push(node->left);if (node->right) que.push(node->right);if (!node->left && !node->right) { // 当左右孩子都为空的时候,说明是最低点的一层了,退出return depth;}}}return depth;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[Python机器学习]:Anaconda3实践环境安装和使用

文章目录 一&#xff1a;机器学习基本环境安装二&#xff1a;设置环境变量三&#xff1a;检查结果四&#xff1a;创建自己的虚拟环境1&#xff1a;查看虚拟环境: conda env list2&#xff1a;创建新环境:conda create --name envname python3.83&#xff1a;删除环境:conda rem…

重温设计模式--观察者模式

文章目录 观察者模式&#xff08;Observer Pattern&#xff09;概述观察者模式UML图作用&#xff1a;实现对象间的解耦支持一对多的依赖关系易于维护和扩展 观察者模式的结构抽象主题&#xff08;Subject&#xff09;&#xff1a;具体主题&#xff08;Concrete Subject&#xf…

【更新】Docker新手入门教程2:在Windows系统通过compose创建多个mysql镜像并配置应用

文章目录 前言一、运行Docker init生成docker配置文件二、修改创建镜像的配置文件1、添加镜像挂载点 三、【拉取镜像】四、生成Docker 镜像查看生成的镜像 五、修改Compose配置文件3、配置Mysql六、生成Docker容器七、检查容器创建状态总结 前言 在window下通过Docker创建mysq…

lxml 解析xml\html

from lxml import etree# XML文档示例 xml_doc """ <root><book><title>Python编程指南</title><author>张三</author></book><book><title>Python高级编程</title><author>李四</autho…

FFmpeg在python里推流被处理过的视频流

链式算法处理视频流 视频源是本地摄像头 # codinggbk # 本地摄像头直接推流到 RTMP 服务器 import cv2 import mediapipe as mp import subprocess as sp# 初始化 Mediapipe mp_drawing mp.solutions.drawing_utils mp_drawing_styles mp.solutions.drawing_styles mp_holis…

从零开始k8s-部署篇(未完待续)

从零开始k8s 1.部署k8s-部署篇 1.部署k8s-部署篇 本次部署完全学习于华子的博客点击此处进入华子主页 K8S中文官网&#xff1a;https://kubernetes.io/zh-cn 笔者从零开始部署的k8s&#xff0c;部署前置条件为 1.需要harbor仓库&#xff0c;存放镜像&#xff0c;拉取镜像&am…

Pytorch | 利用AI-FGTM针对CIFAR10上的ResNet分类器进行对抗攻击

Pytorch | 利用AI-FGTM针对CIFAR10上的ResNet分类器进行对抗攻击 CIFAR数据集AI-FGTM介绍算法流程初始化迭代更新&#xff08; t 0 t 0 t0 到 T − 1 T - 1 T−1&#xff09;迭代完成 AI-FGTM代码实现AI-FGTM算法实现攻击效果 代码汇总aifgtm.pytrain.pyadvtest.py 之前已经…

视频监控平台:Liveweb视频汇聚融合平台智慧安防视频监控应用方案

Liveweb是一款功能强大、灵活部署的安防视频监控平台&#xff0c;支持多种主流标准协议&#xff0c;包括GB28181、RTSP/Onvif、RTMP等&#xff0c;同时兼容海康Ehome、海大宇等厂家的私有协议和SDK接入。该平台不仅提供传统安防监控功能&#xff0c;还支持接入AI智能分析&#…

【Linux系列】Shell 脚本中的条件判断:`[ ]`与`[[ ]]`的比较

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

【LLM论文日更】| 训练大型语言模型在连续潜在空间中进行推理

论文&#xff1a;https://arxiv.org/pdf/2412.06769代码&#xff1a;暂未开源机构 &#xff1a;Meta领域&#xff1a;思维链发表&#xff1a;arxiv 研究背景 研究问题&#xff1a;这篇文章要解决的问题是如何在大语言模型&#xff08;LLMs&#xff09;中实现一种新的推理范式&…

opc da 服务器数据 转 opc ua项目案例

目录 1 案例说明 2 VFBOX网关工作原理 3 应用条件 4 查看OPC DA服务器的相关参数 5 配置网关采集opc da数据 6 用opc ua协议转发采集的数据 7 在服务器上运行仰科OPC DA采集软件 8 案例总结 1 案例说明 在OPC DA服务器上运行OPC DA client软件查看OPC DA服务器的相关参…

05.HTTPS的实现原理-HTTPS的握手流程(TLS1.2)

05.HTTPS的实现原理-HTTPS的握手流程&#xff08;TLS1.2&#xff09; 简介1. TLS握手过程概述2. TLS握手过程细化3. 主密钥&#xff08;对称密钥&#xff09;生成过程4. 密码规范变更 简介 主要讲述了混合加密流程完成后&#xff0c;客户端和服务器如何共同获得相同的对称密钥…

Excel粘贴复制不完整的原因以及解决方法

在数据处理和分析的过程中&#xff0c;Excel无疑是不可或缺的工具。然而&#xff0c;在使用Excel进行复制粘贴操作时&#xff0c;有时会遇到粘贴不完整的情况&#xff0c;这可能会让人感到困惑和烦恼。本文将深入探讨Excel粘贴复制不完整的原因、提供解决方案&#xff0c;并给出…

数据中台从centos升级为国产操作系统后,资源增加字段时,提交报500错误

文章目录 背景一、步骤1.分析阶段2.查看nginx3.修改用户&#xff08;也可以修改所有者权限&#xff09; 背景 故障报错&#xff1a; nginx报错信息&#xff1a; 2024/12/19 15:25:31 [crit, 500299#0: *249 onen0 " /var/lib/nginx/tmp/cient body/0000000001" f…

在Windows11上编译C#的实现Mono的步骤

在Windows11上编译Mono的步骤 1、 在win11打开开发者模式,在更新和安全选项里,如下图: 2、下载并安装64位的cygwin, 下载网站:www.cygwin.com 3、 安装 Visual Studio 2015 or later 的社区版本。 4、 下载Mono的windows最新版本。 5、 在cmd.exe里运行下面的命令来安…

我的创作纪念日(五年)

慕然回首 平平无奇的周一早晨&#xff0c;收到来自csdn的提醒&#xff0c;创作纪念日五周年了&#xff0c;这也意味着我从事开发行业差不多有整整五年了&#xff0c;五年啊&#xff01;你知道这五年我是怎么过的吗&#xff1f;一句Just do IT&#xff0c;我做it整整做了五年&am…

python+reportlab创建PDF文件

目录 字体导入 画布写入 创建画布对象 写入文本内容 写入图片内容 新增页 画线 表格 保存 模板写入 创建模板对象 段落及样式 表格及样式 画框 图片 页眉页脚 添加图形 构建pdf文件 reportlab库支持创建包含文本、图像、图形和表格的复杂PDF文档。 安装&…

人工智能ACA(七)——计算机视觉基础

一、自然语言处理基本介绍 1. 自然语言处理的定义 1-1 自然语言 人类使用的在社会生活中自然形成的语言 1-2 自然语言处理 目标是让计算机能够理解、解析、生成和处理人类的自然语言 包含自然语言理解和自然语言生成两部分组成 2. 自然语言处理的发展趋势 3.自然语言处理…

Ubuntu20.04 交叉编译Qt5.15.15 for rk3588

rk3588编译Qt搞了我大半年了&#xff0c;一直困惑特别鸣谢&#xff1a;qq1033878279的网友远程帮我编译演示了一遍。 一、vmware 安装基础工具 sudo apt install -y build-essential net-tools openssh-server vim openssl libssl-dev 二、vmware 下载 cmake和Qt源码 下载cm…

使用开源在线聊天工具Fiora轻松搭建个性化聊天平台在线交流

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家&#xff1a;人工智能教程 文章目录 前言1.关于Fiora2.安装Docker3.本地部署Fiora4.使用Fiora5.cpolar内网穿透工具安装6.创建远程连接公网地址7.固定Uptime …