代码随想录训练营二刷第十五天 | 层序遍历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. 二叉树的层序遍历 题目链接:https://leetcode.cn/problems/binary-tree-level-order-traversal/ 思路:两次while,内层控制每一行的数量,…...

nowcoder NC10 大数乘法
题目链接: 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. 每日温度 输入一个数组,找比i天温度高的第一天 知识点:单调栈 状态:看思路自己写 思路: 看自己写的注释,维护一个单调栈 // 版本一 class Solution { public:vector<int> dailyTemperatures(vector<…...
【Luogu】 P5445 [APIO2019] 路灯
题目链接 点击打开链接 题目解法 转化很妙 考虑关路灯 x x x 的操作 令左边第一个未关的路灯为 L L L,右边第一个未关的路灯为 R R R,那么这一次会影响的区间即为 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、案例需求 创建一个独立消费者,消费firstTopic主题 0 号分区的数据,所下图所示: 1.2、案…...

基于Simulink的用于电力系统动态分析
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...

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

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

GPT引领前沿与应用突破之GPT4科研实践技术与AI绘图教程
详情点击链接:GPT引领前沿与应用突破之GPT4科研实践技术与AI绘图教程 前沿 GPT对于每个科研人员已经成为不可或缺的辅助工具,不同的研究领域和项目具有不同的需求。 如在科研编程、绘图领域: 1、编程建议和示例代码: 无论你使用的编程语言是…...
Git上传新项目
第一步:初始化 Git 仓库 首先,打开终端或命令行界面,然后导航到项目目录。运行下面的命令来初始化一个新的 Git 仓库: git init这将创建一个新的 .git 子目录,其中包含了初始化的 Git 仓库。 第二步:添加…...
C语言文件操作总结
目录 字符方式读入文件 数据块方式读写文件 文件定位与随机读写 文件中数据的修改 字符方式读入文件 1.向文件中写入(输入字符) 用 fputc 函数或 puts 函数可以把一个字符写到磁盘文件中去。 int fputc(int ch,FILE * fp) ch 是要输出的字符&#…...
原生js之dom如何进行事件监听(事件捕获/冒泡)
那么好,这次主要讲解的就是dom是如何进行事件监听和事件取消监听的,我们知道vue中主要用watch来进行监听. js监听与取消监听 那么原生js主要用到的就是addListenEvent事件来进行监听,可以监听文档dom对象也可以监听浏览器bom对象,监听事件的语法结构如下 Dom/Bom监听 eleme…...

使用SimPowerSystems并网光伏阵列研究(Simulink实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...

BUUCTF-WEB-[ACTF2020 新生赛]Includel
打开靶机 点击tips 利用Burp抓包,未见异常 但发现了响应头是 PHP/7.3.13 想到了"php://input"伪协议POST发送PHP代码 构建Payload:?filephp://filter/readconvert.base64-encode/resourceflag.php 这里需要注意的是使用php://filter伪协议…...
算法通关村十四关:白银挑战-堆能高效解决的经典问题
白银挑战-堆能高效解决的经典问题 1.在数组中找第K大的元素 LeetCode215 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 思路分析 主要解决方法有3个,选择法,堆查找法和快速排序法 方法1:选择法 先遍历一遍找到最大的…...

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

从0到1实现播放控制器
这系列文章主要讲诉如何从0到1使用QT实现带时间显示、滚动字幕等的自定义配置视频播放控制器。平时我们乘坐地铁经常看到各条线的播放控制器都大同小异。其实都是通过QT等界面开发软件来实现的。 在具体开发之前,需要明确我们需要做什么? 1. 开发一个可…...
【Vue-Element-Admin】导出el-table全部数据
背景 因为el-table实现了分页查询,所以想要实现el-table需要重新编写一个查询全部数据的方法 查询全部数据 listQuery: export default{return{listQuery:{//page:1,//limit:20,//如果想兼容按条件导出,可以定义查询条件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);//其它控件࿰…...
【向量数据库】相似向量检索Faiss数据库的安装及余弦相似度计算(C++)
目录 简介安装方法安装OpenBLAS安装lapack编译Faiss 代码示例余弦相似度计算输出ID号而非索引的改进版 简介 Faiss 是一个强大的向量相似度搜索库,具有以下优点: 高效的搜索性能:Faiss 在处理大规模向量数据时表现出色。它利用了高度优化的索…...

idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...

前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...

Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...