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

算法学习——LeetCode力扣二叉树篇3

算法学习——LeetCode力扣二叉树篇3

在这里插入图片描述

116. 填充每个节点的下一个右侧节点指针

116. 填充每个节点的下一个右侧节点指针 - 力扣(LeetCode)

描述

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

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

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

初始状态下,所有 next 指针都被设置为 NULL。

示例

示例 1:

在这里插入图片描述

输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,‘#’ 标志着每一层的结束。

示例 2:

输入:root = []
输出:[]

提示

  • 树中节点的数量在 [0, 212 - 1] 范围内
  • -1000 <= node.val <= 1000

进阶

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。

代码解析

/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}Node(int _val, Node* _left, Node* _right, Node* _next): val(_val), left(_left), right(_right), next(_next) {}
};
*/class Solution {
public:Node* connect(Node* root) {Node* result;Node*  node ; //迭代节点queue<Node* > my_que; //队列if(root == nullptr) return root;else // 根节点进队列{my_que.push(root);}while(my_que.empty() != 1){int size = my_que.size(); for(int i=0 ; i<size ; i++) {node = my_que.front(); //该层级的点弹出放入数组my_que.pop();if(i<size-1)//如果该节点不是该层次的最后一个,next指针连接下一个{node->next = my_que.front();}else//该节点是该层次的最后一个,next连接空{node->next = nullptr;}//每一个弹出点的下一个层级左右节点压入队列if(node->left != nullptr)    my_que.push(node->left);if(node->right != nullptr)   my_que.push(node->right);}}return root;}
};

117. 填充每个节点的下一个右侧节点指针 II

117. 填充每个节点的下一个右侧节点指针 II - 力扣(LeetCode)

描述

给定一个二叉树:

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

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

初始状态下,所有 next 指针都被设置为 NULL 。

示例

示例 1:
在这里插入图片描述

输入:root = [1,2,3,4,5,null,7]
输出:[1,#,2,3,#,4,5,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化输出按层序遍历顺序(由 next 指针连接),‘#’ 表示每层的末尾。

示例 2:

输入:root = []
输出:[]

提示

树中的节点数在范围 [0, 6000] 内
-100 <= Node.val <= 100

进阶

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求,本题中递归程序的隐式栈空间不计入额外空间复杂度。

代码解析

/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}Node(int _val, Node* _left, Node* _right, Node* _next): val(_val), left(_left), right(_right), next(_next) {}
};
*/class Solution {
public:Node* connect(Node* root) {queue<Node*> my_que;  if( root == nullptr ) return root;else my_que.push(root);while(my_que.size() != 0){int size = my_que.size();for(int i=0 ; i<size ;i++){Node* tmp_node = my_que.front();my_que.pop();if(i == size-1) tmp_node->next = nullptr;else tmp_node->next = my_que.front();if(tmp_node->left != nullptr) my_que.push(tmp_node->left);if(tmp_node->right != nullptr) my_que.push(tmp_node->right);}}return root;}
};

104. 二叉树的最大深度

104. 二叉树的最大深度 - 力扣(LeetCode)

描述

给定一个二叉树 root ,返回其最大深度。

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

示例

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:3

示例 2:

输入:root = [1,null,2]
输出:2

提示

  • 树中节点的数量在 [0, 104] 区间内。
  • -100 <= Node.val <= 100

代码解析

层次遍历
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {TreeNode* node ; //迭代节点queue<TreeNode*> my_que; //队列int result = 0;if(root == nullptr) return result;else // 根节点进队列{my_que.push(root);}while(my_que.empty() != 1){int size = my_que.size();result +=1;//计算层级数量for(int i=0 ; i<size ; i++) {node = my_que.front(); //该层级的点弹出放入数组my_que.pop();//每一个弹出点的下一个层级左右节点压入队列if(node->left != nullptr)    my_que.push(node->left);if(node->right != nullptr)   my_que.push(node->right);}}return result;}
};
递归遍历
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int getdepth(TreeNode* root){if(root==nullptr) return 0;int left_depth = getdepth(root->left);int right_depth = getdepth(root->right);return 1+max(left_depth , right_depth);}int maxDepth(TreeNode* root) {if(root == nullptr) return 0;return getdepth(root);}
};

111. 二叉树的最小深度

111. 二叉树的最小深度 - 力扣(LeetCode)

描述

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

示例

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:

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

提示

  • 树中节点数的范围在 [0, 105] 内
  • -1000 <= Node.val <= 1000

代码解析

层次遍历
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int minDepth(TreeNode* root) {TreeNode* node ; //迭代节点queue<TreeNode*> my_que; //队列int result = 0;vector<int> min_num;if(root == nullptr) return result;else // 根节点进队列{my_que.push(root);}while(my_que.empty() != 1){int size = my_que.size();result +=1;for(int i=0 ; i<size ; i++) {node = my_que.front(); //该层级的点弹出放入数组my_que.pop();// cout<<node->val<<' '<<node->left<<' '<<node->right<<endl;//每一个弹出点的下一个层级左右节点压入队列if(node->left != nullptr)    my_que.push(node->left);if(node->right != nullptr)   my_que.push(node->right);//找到叶子节点if(node->left == nullptr && node->right == nullptr)  min_num.push_back(result);}}//排序找到叶子节点所在最小层sort(min_num.begin(),min_num.end());return min_num[0];}
};
递归法
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int getdepth(TreeNode* cur){if(cur == nullptr) return 0;int right_depth , left_depth;//左子树为空,直接测量右子树if(cur->left == nullptr && cur->right != nullptr){right_depth = getdepth(cur->right);return 1 + right_depth;}else if(cur->left != nullptr && cur->right == nullptr) //右子树为空,直接测量左子树{left_depth = getdepth(cur->left);return 1 + left_depth;}else//左右子树都为空或都不为空,左右子树均测量,返回最小值{left_depth = getdepth(cur->left);right_depth = getdepth(cur->right);return 1 +  min(left_depth,right_depth);}}int minDepth(TreeNode* root) {if(root == nullptr) return 0;return getdepth(root);}
};

相关文章:

算法学习——LeetCode力扣二叉树篇3

算法学习——LeetCode力扣二叉树篇3 116. 填充每个节点的下一个右侧节点指针 116. 填充每个节点的下一个右侧节点指针 - 力扣&#xff08;LeetCode&#xff09; 描述 给定一个 完美二叉树 &#xff0c;其所有叶子节点都在同一层&#xff0c;每个父节点都有两个子节点。二叉树…...

强制卸载挂载目录

当遇到磁盘卸载失败提示 device is busy fuser -a 显示所有命令行中指定的文件&#xff0c;默认情况下被访问的文件才会被显示。 -c 和-m一样&#xff0c;用于POSIX兼容。 -k 杀掉访问文件的进程。如果没有指定-signal就会发送SIGKILL信号。结合 –signal -signal 使用指定的信…...

HiveSQL——sum(if()) 条件累加

注&#xff1a;参考文章&#xff1a; HiveSql面试题10--sum(if)统计问题_hive sum if-CSDN博客文章浏览阅读5.8k次&#xff0c;点赞6次&#xff0c;收藏19次。0 需求分析t_order表结构字段名含义oid订单编号uid用户idotime订单时间&#xff08;yyyy-MM-dd&#xff09;oamount订…...

Linux命令行工具使用HTTP代理的方法详解

亲爱的Linux用户们&#xff0c;有没有想过在命令行世界里&#xff0c;你的每一个指令都能悄无声息地穿越千山万水&#xff0c;而不被外界窥探&#xff1f;哈哈&#xff0c;没错&#xff0c;就是通过HTTP代理&#xff01;今天&#xff0c;我们就来一起探索如何在Linux命令行工具…...

idea mavn 中途新建gitignore文件如何生效

两种情况下项目代码中新建gitignore文件如何生效。 第一种情况项目代码下没有模块的情况 直接在该项目代码的根目录下进入git命令行执行&#xff1a; git rm -r --cached . git add . 注意上面两个命令后面都有一个点 第二种情况是有模块的情况 需要进入模块目录执行上…...

Hadoop:认识MapReduce

MapReduce是一个用于处理大数据集的编程模型和算法框架。其优势在于能够处理大量的数据&#xff0c;通过并行化来加速计算过程。它适用于那些可以分解为多个独立子任务的计算密集型作业&#xff0c;如文本处理、数据分析和大规模数据集的聚合等。然而&#xff0c;MapReduce也有…...

9.4 OpenGL帧缓冲:纹理和帧缓冲之间的反馈循环

纹理和帧缓冲之间的反馈循环 Feedback Loops Between Textures and the Framebuffer 当在图形编程中&#xff0c;特别是OpenGL这样的图形API中处理纹理&#xff08;Texture&#xff09;和帧缓冲区&#xff08;Framebuffer&#xff09;时&#xff0c;可能会出现一种称为“反馈循…...

相机图像质量研究(6)常见问题总结:光学结构对成像的影响--对焦距离

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…...

fast.ai 机器学习笔记(二)

机器学习 1&#xff1a;第 5 课 原文&#xff1a;medium.com/hiromi_suenaga/machine-learning-1-lesson-5-df45f0c99618 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 来自机器学习课程的个人笔记。随着我继续复习课程以“真正”理解它&#xff0c;这些笔记将继续更…...

vue3 elementplus DateTimePicker 日期时间设置默认时间为当天

DateTimePicker里面有个自带属性 可以实现这个需求&#xff0c;如图&#xff1a; // 设置当前当天时间范围 00: 00: 00 - 23:59:59 const currentDate [setDefaultDate(0), setDefaultDate(1)]const setDefaultDate (type:number ): string > {let t ;let date new Da…...

2024年笔记--centos docker离线安装启动失败

Failed to start Docker Application Container Engine 错误如下&#xff1a; [rootel70 docker]# systemctl start docker.service Job for docker.service failed because start of the service was attempted too often. See "systemctl status docker.service" …...

2024.2.10 DMS(数据库管理系统)初体验

数据库管理系统(Database Management System)是一种操纵和管理数据库的大型软件&#xff0c;用于建立、使用和维护数据库&#xff0c;简称DBMS。它对数据库进行统一的管理和控制&#xff0c;以保证数据库的安全性和完整性。用户通过DBMS访问数据库中的数据&#xff0c;数据库管…...

zk集群--集群同步

1.概述 前面一章分析了集群下启动阶段选举过程&#xff0c;一旦完成选举&#xff0c;通过执行QuorumPeer的setPeerState将设置好选举结束后自身的状态。然后&#xff0c;将再次执行QuorumPeer的run的新的一轮循环&#xff0c; QuorumPeer的run的每一轮循环&#xff0c;先判断…...

复习面经哦

1.函数可以变量提升 JavaScript 中的函数存在变量提升的概念&#xff0c;这意味着在执行代码之前&#xff0c;函数声明会被提升到其作用域的顶部。这使得你可以在函数声明之前调用函数。然而&#xff0c;这种行为只适用于函数声明&#xff0c;而不是函数表达式。 下面是一些关…...

c++ STL系列——(二)vector

引言 在现代C编程中&#xff0c;std::vector是最常用的动态数组实现之一&#xff0c;它是C标准模板库&#xff08;STL&#xff09;的一部分。vector提供了一种方式&#xff0c;以单一数据结构来存储元素集合&#xff0c;并且可以动态地调整大小以适应新元素。本文将深入探讨ve…...

STM32能够做到数据采集和发送同时进行吗?

STM32能够做到数据采集和发送同时进行吗&#xff1f; 在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「STM32的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&am…...

5.Swift常量

Swift 常量 在 Swift 中&#xff0c;除了可以声明变量&#xff08;使用 var 关键字&#xff09;&#xff0c;还可以声明常量&#xff08;使用 let 关键字&#xff09;。常量在赋值后就不能再修改其值&#xff0c;适合用于存储不会改变的数据。以下是关于 Swift 常量的一些重要…...

Linux运行级别 | 管理Linux服务

Linux运行级别 级别&#xff1a; 0关机1单用户2多用户但是不运行nfs网路文件系统3默认的运行级别&#xff0c;给一个黑的屏幕&#xff0c;只能敲命令4未使用5默认的运行级别&#xff0c;图形界面6重启切换运行级别&#xff1a; init x管理Linux服务 systemctl命令&#xf…...

Nginx 配置 SSL证书

成功配置SSL证书后&#xff0c;您将能够通过HTTPS加密通道安全访问Nginx服务器。 一、准备材料 SSL证书绑定的域名已完成DNS解析&#xff0c;即您的域名与主机IP地址相互映射。您可以通过DNS验证证书工具&#xff0c;检测域名DNS解析是否生效。具体操作&#xff1a; 【1】登录…...

如何正确理解和获取S参数

S参数是网络参数&#xff0c;定义了反射波和入射波之间的关系&#xff0c;给定频率的S参数矩阵指定端口反射波b的矢量相对于端口入射波a的矢量&#xff0c;如下所示&#xff1a; bS∙a 在此基础上&#xff0c;如下图所示&#xff0c;为一个常见的双端口网络拓扑图&#xff1a;…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...