当前位置: 首页 > 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 在处理大规模向量数据时表现出色。它利用了高度优化的索…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

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

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

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...