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

代码随想录训练营二刷第十五天 | 层序遍历10道 226.翻转二叉树 101.对称二叉树 2

代码随想录训练营二刷第十五天 | 层序遍历10道 226.翻转二叉树 101.对称二叉树 2

一、102. 二叉树的层序遍历

题目链接:https://leetcode.cn/problems/binary-tree-level-order-traversal/
思路:两次while,内层控制每一行的数量,数量是添加的子节点的个数。

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {LinkedList<TreeNode> queue = new LinkedList<>();List<List<Integer>> result = new ArrayList<>();if (root == null) return result;queue.add(root);while (!queue.isEmpty()) {List<Integer> list = new ArrayList<>();int num = queue.size();while (num > 0) {TreeNode node = queue.poll();list.add(node.val);num--;if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}result.add(list);}return result;}
}

二、107. 二叉树的层序遍历 II

题目链接:https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
思路:正常的层序遍历,结束后翻转数组。

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> arrayLists = new ArrayList<>();LinkedList<TreeNode> queue = new LinkedList<>();if (root == null) return arrayLists;queue.add(root);while (!queue.isEmpty()) {int len = queue.size();List<Integer> list = new ArrayList<>();while (len > 0) {TreeNode node = queue.poll();list.add(node.val);len--;if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}arrayLists.add(list);}int i = 0, j = arrayLists.size() - 1;while (i < j) {List<Integer> temp = arrayLists.get(i);arrayLists.set(i, arrayLists.get(j));arrayLists.set(j, temp);i++;j--;}return arrayLists;}
}

三、199. 二叉树的右视图

题目链接:https://leetcode.cn/problems/binary-tree-right-side-view/
思路:正常层序遍历,只有每层最后一个才加入结果集。

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> list = new ArrayList<>();LinkedList<TreeNode> queue = new LinkedList<>();if (root == null) return list;queue.add(root);while (!queue.isEmpty()) {int len = queue.size();while (len > 0) {TreeNode node = queue.poll();if (len == 1) list.add(node.val);len--;if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}}return list;}
}

四、637. 二叉树的层平均值

题目链接:https://leetcode.cn/problems/average-of-levels-in-binary-tree/
思路:正常层序遍历。

class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> list = new ArrayList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int len = queue.size();Double sum = 0.0;for (int i = 0; i < len; i++) {TreeNode node = queue.poll();sum += node.val;if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}list.add(sum / len);}return list;}
}

五、429. N 叉树的层序遍历

题目链接:https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
思路:常规层序遍历注意空指针。


class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> arrayLists = new ArrayList<>();LinkedList<Node> queue = new LinkedList<>();if (root == null) return arrayLists;queue.add(root);while (!queue.isEmpty()) {int len = queue.size();List<Integer> list = new ArrayList<>();for (int i = 0; i < len; i++) {Node node = queue.poll();list.add(node.val);for (Node child : node.children) {if (child != null) queue.add(child);}}arrayLists.add(list);}return arrayLists;}
}

六、515. 在每个树行中找最大值

题目链接:https://leetcode.cn/problems/find-largest-value-in-each-tree-row/
思路:正常层序遍历。

class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> list = new ArrayList<>();LinkedList<TreeNode> queue = new LinkedList<>();if (root == null) return list;queue.add(root);while (!queue.isEmpty()) {int len = queue.size(), max = Integer.MIN_VALUE;for (int i = 0; i < len; i++) {TreeNode node = queue.poll();max = Math.max(max, node.val);if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}list.add(max);}return list;}
}

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

题目链接:https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
思路:层序遍历

class Solution {public Node connect(Node root) {if (root == null) return root;LinkedList<Node> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int len = queue.size();while (len > 0) {Node node = queue.poll();if (len > 1) node.next = queue.peek();len--;if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}}return root;}
}

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

题目链接:https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/
思路:和上一题一样。

class Solution {public Node connect(Node root) {if (root == null) return root;LinkedList<Node> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int len = queue.size();while (len > 0) {Node node = queue.poll();if (len > 1) node.next = queue.peek();len--;if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}}return root;}
}

九、104. 二叉树的最大深度

题目链接:https://leetcode.cn/problems/maximum-depth-of-binary-tree/
思路:层序遍历。

class Solution {public int maxDepth(TreeNode root) {if (root == null) return 0;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);int deep = 0;while (!queue.isEmpty()) {int len = queue.size();for (int i = 0; i < len; i++) {TreeNode node = queue.poll();if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}deep++;}return deep;}
}

十、111. 二叉树的最小深度

题目链接:https://leetcode.cn/problems/minimum-depth-of-binary-tree/
思路:层序遍历提早返回。

class Solution {public int minDepth(TreeNode root) {if (root == null) return 0;LinkedList<TreeNode> queue = new LinkedList<>();int deep = 0;queue.add(root);while (!queue.isEmpty()) {int len = queue.size();for (int i = 0; i < len; i++) {TreeNode node = queue.poll();if (node.left == null && node.right == null) {return ++deep;}if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}deep++;}return deep;}
}

十一、226.翻转二叉树

题目链接:https://leetcode.cn/problems/invert-binary-tree/
思路:前序遍历交换

class Solution {public TreeNode invertTree(TreeNode root) {reserve(root);return root;}void reserve(TreeNode node) {if (node == null)return;TreeNode temp = node.left;node.left = node.right;node.right = temp;reserve(node.left);reserve(node.right);}
}

十二、101.对称二叉树 2

题目链接:https://leetcode.cn/problems/symmetric-tree/
思路:把一棵树分成两颗树进行比较

class Solution {boolean flag = true;public boolean isSymmetric(TreeNode root) {equal(root.left, root.right);return flag;}void equal(TreeNode node1, TreeNode node2) {if (node1 == null && node2 == null) {}else if (node1 != null && node2 != null) {if (node1.val != node2.val) {flag = false;}else {equal(node1.left, node2.right);equal(node1.right, node2.left);}}else {flag = false;}}
}

相关文章:

代码随想录训练营二刷第十五天 | 层序遍历10道 226.翻转二叉树 101.对称二叉树 2

代码随想录训练营二刷第十五天 | 层序遍历10道 226.翻转二叉树 101.对称二叉树 2 一、102. 二叉树的层序遍历 题目链接&#xff1a;https://leetcode.cn/problems/binary-tree-level-order-traversal/ 思路&#xff1a;两次while&#xff0c;内层控制每一行的数量&#xff0c…...

nowcoder NC10 大数乘法

题目链接&#xff1a; https://www.nowcoder.com/practice/c4c488d4d40d4c4e9824c3650f7d5571?tpId196&tqId37177&rp1&ru/exam/company&qru/exam/company&sourceUrl%2Fexam%2Fcompany&difficultyundefined&judgeStatusundefined&tags&tit…...

非科班菜鸡算法学习记录 | 代码随想录算法训练营第58天|| 单调栈! 739. 每日温度 496.下一个更大元素 I

739. 每日温度 输入一个数组&#xff0c;找比i天温度高的第一天 知识点&#xff1a;单调栈 状态&#xff1a;看思路自己写 思路&#xff1a; 看自己写的注释&#xff0c;维护一个单调栈 // 版本一 class Solution { public:vector<int> dailyTemperatures(vector<…...

【Luogu】 P5445 [APIO2019] 路灯

题目链接 点击打开链接 题目解法 转化很妙 考虑关路灯 x x x 的操作 令左边第一个未关的路灯为 L L L&#xff0c;右边第一个未关的路灯为 R R R&#xff0c;那么这一次会影响的区间即为 l ∈ [ L 1 , x ] , r ∈ [ x , R − 1 ] l\in[L1,x],\;r\in[x,R-1] l∈[L1,x],…...

Kafka3.0.0版本——消费者(独立消费者消费某一个主题中某个分区数据案例__订阅分区)

目录 一、独立消费者消费某一个主题中某个分区数据案例1.1、案例需求1.2、案例代码1.3、测试 一、独立消费者消费某一个主题中某个分区数据案例 1.1、案例需求 创建一个独立消费者&#xff0c;消费firstTopic主题 0 号分区的数据&#xff0c;所下图所示&#xff1a; 1.2、案…...

基于Simulink的用于电力系统动态分析

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

日200亿次调用,喜马拉雅网关的架构设计

说在前面 在40岁老架构师 尼恩的读者社区(50)中&#xff0c;很多小伙伴拿到一线互联网企业如阿里、网易、有赞、希音、百度、滴滴的面试资格。 最近&#xff0c;尼恩指导一个小伙伴简历&#xff0c;写了一个《API网关项目》&#xff0c;此项目帮这个小伙拿到 字节/阿里/微博/…...

构造函数和析构函数(个人学习笔记黑马学习)

构造函数:主要作用在于创建对象时为对象的成员属性赋值&#xff0c;构造函数由编译器自动调用&#xff0c;无须手动调用。析构函数:主要作用在于对象销毁前系统自动调用&#xff0c;执行一些清理工作。 #include <iostream> using namespace std;//对象初始化和清理class…...

GPT引领前沿与应用突破之GPT4科研实践技术与AI绘图教程

详情点击链接&#xff1a;GPT引领前沿与应用突破之GPT4科研实践技术与AI绘图教程 前沿 GPT对于每个科研人员已经成为不可或缺的辅助工具&#xff0c;不同的研究领域和项目具有不同的需求。 如在科研编程、绘图领域&#xff1a; 1、编程建议和示例代码: 无论你使用的编程语言是…...

Git上传新项目

第一步&#xff1a;初始化 Git 仓库 首先&#xff0c;打开终端或命令行界面&#xff0c;然后导航到项目目录。运行下面的命令来初始化一个新的 Git 仓库&#xff1a; git init这将创建一个新的 .git 子目录&#xff0c;其中包含了初始化的 Git 仓库。 第二步&#xff1a;添加…...

C语言文件操作总结

目录 字符方式读入文件 数据块方式读写文件 文件定位与随机读写 文件中数据的修改 字符方式读入文件 1.向文件中写入&#xff08;输入字符&#xff09; 用 fputc 函数或 puts 函数可以把一个字符写到磁盘文件中去。 int fputc(int ch,FILE * fp) ch 是要输出的字符&#…...

原生js之dom如何进行事件监听(事件捕获/冒泡)

那么好,这次主要讲解的就是dom是如何进行事件监听和事件取消监听的,我们知道vue中主要用watch来进行监听. js监听与取消监听 那么原生js主要用到的就是addListenEvent事件来进行监听,可以监听文档dom对象也可以监听浏览器bom对象,监听事件的语法结构如下 Dom/Bom监听 eleme…...

使用SimPowerSystems并网光伏阵列研究(Simulink实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

BUUCTF-WEB-[ACTF2020 新生赛]Includel

打开靶机 点击tips 利用Burp抓包&#xff0c;未见异常 但发现了响应头是 PHP/7.3.13 想到了"php://input"伪协议POST发送PHP代码 构建Payload&#xff1a;?filephp://filter/readconvert.base64-encode/resourceflag.php 这里需要注意的是使用php://filter伪协议…...

算法通关村十四关:白银挑战-堆能高效解决的经典问题

白银挑战-堆能高效解决的经典问题 1.在数组中找第K大的元素 LeetCode215 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 思路分析 主要解决方法有3个&#xff0c;选择法&#xff0c;堆查找法和快速排序法 方法1&#xff1a;选择法 先遍历一遍找到最大的…...

跨站请求伪造(CSRF)攻击与防御原理

跨站请求伪造&#xff08;CSRF&#xff09; 1.1 CSRF原理 1.1.1 基本概念 跨站请求伪造&#xff08;Cross Site Request Forgery&#xff0c;CSRF&#xff09;是一种攻击&#xff0c;它强制浏览器客户端用户在当前对其进行身份验证后的Web 应用程序上执行非本意操作的攻击&a…...

从0到1实现播放控制器

这系列文章主要讲诉如何从0到1使用QT实现带时间显示、滚动字幕等的自定义配置视频播放控制器。平时我们乘坐地铁经常看到各条线的播放控制器都大同小异。其实都是通过QT等界面开发软件来实现的。 在具体开发之前&#xff0c;需要明确我们需要做什么&#xff1f; 1. 开发一个可…...

【Vue-Element-Admin】导出el-table全部数据

背景 因为el-table实现了分页查询&#xff0c;所以想要实现el-table需要重新编写一个查询全部数据的方法 查询全部数据 listQuery: export default{return{listQuery:{//page:1,//limit:20,//如果想兼容按条件导出&#xff0c;可以定义查询条件age:undefined,sex:undefined…...

MFC 更改控件的大小和位置

获取当前主窗体的位置rect CRect dlgNow;GetWindowRect(&dlgNow);获取某一个控件当前的位置 CRect rect;CButton* pBtn (CButton*)GetDlgItem(IDC_BUTTONXXX);//获取按钮控件pBtn->GetWindowRect(rect);CWnd* pWnd(CWnd*)GetDlgItem(IDC_EDITXXX);//其它控件&#xff0…...

【向量数据库】相似向量检索Faiss数据库的安装及余弦相似度计算(C++)

目录 简介安装方法安装OpenBLAS安装lapack编译Faiss 代码示例余弦相似度计算输出ID号而非索引的改进版 简介 Faiss 是一个强大的向量相似度搜索库&#xff0c;具有以下优点&#xff1a; 高效的搜索性能&#xff1a;Faiss 在处理大规模向量数据时表现出色。它利用了高度优化的索…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...

rm视觉学习1-自瞄部分

首先先感谢中南大学的开源&#xff0c;提供了很全面的思路&#xff0c;减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接&#xff1a;https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架&#xff1a; 代码框架结构&#xff1a;readme有…...

使用ch340继电器完成随机断电测试

前言 如图所示是市面上常见的OTA压测继电器&#xff0c;通过ch340串口模块完成对继电器的分路控制&#xff0c;这里我编写了一个脚本方便对4路继电器的控制&#xff0c;可以设置开启时间&#xff0c;关闭时间&#xff0c;复位等功能 软件界面 在设备管理器查看串口号后&…...