力扣labuladong——一刷day43
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、力扣257. 二叉树的所有路径
- 二、力扣129. 求根节点到叶节点数字之和
- 三、力扣199. 二叉树的右视图
- 四、力扣662. 二叉树最大宽度
前言
一般来说,如果让你在二叉树的「树枝」上做文章,那么用遍历的思维模式解题是比较自然的想法
一、力扣257. 二叉树的所有路径
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {List<String> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<String> binaryTreePaths(TreeNode root) {fun(root);return res;}public void fun(TreeNode root){if(root == null){return;}if(root.left == null && root.right == null){StringBuilder sb = new StringBuilder();for(int i = 0; i < path.size();i ++){sb.append(path.get(i)).append("->");}sb.append(root.val);res.add(sb.toString());return;}path.add(root.val);fun(root.left);fun(root.right);path.remove(path.size()-1);}
}
二、力扣129. 求根节点到叶节点数字之和
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {int sum = 0, path = 0;public int sumNumbers(TreeNode root) {fun(root);return sum;}public void fun(TreeNode root){if(root == null){return;}if(root.left == null && root.right == null){path = (path * 10 + root.val);System.out.println(path);sum += path;path /= 10;return;}path = (path * 10 + root.val);fun(root.left);fun(root.right);path /= 10;}
}
更高效的解法
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {int sum = 0;StringBuilder sb = new StringBuilder();public int sumNumbers(TreeNode root) {fun(root);return sum;}public void fun(TreeNode root){if(root == null){return;}sb.append(root.val);if(root.left == null && root.right == null){sum += Integer.parseInt(sb.toString());sb.deleteCharAt(sb.length()-1);return;}fun(root.left);fun(root.right);sb.deleteCharAt(sb.length()-1);}
}
三、力扣199. 二叉树的右视图
层序遍历
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {Deque<TreeNode> deq = new LinkedList<>();public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new LinkedList<>();if(root == null){return res;}deq.offerLast(root);while(!deq.isEmpty()){int len = deq.size();TreeNode temp = deq.peekLast();res.add(temp.val);for(int i = 0; i <len; i ++){TreeNode cur = deq.pollFirst();if(cur.left != null){deq.offerLast(cur.left);}if(cur.right != null){deq.offerLast(cur.right);}}}return res;}
}
深度优先搜索
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {int depth = 0;List<Integer> res = new ArrayList<>();public List<Integer> rightSideView(TreeNode root) {fun(root);return res;}public void fun(TreeNode root){if(root == null){return;}depth ++;if(depth > res.size()){res.add(root.val);}fun(root.right);fun(root.left);depth --;}
}
四、力扣662. 二叉树最大宽度
层序遍历,采用完全二叉树的编号顺序给二叉树编号,当前节点为i,左孩子为2*i,右孩子为2*i+1,层序遍历时记录每层第一个和最后一个元素的序号,即可得出本层的宽度
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {class Pair{TreeNode node;int id;public Pair(TreeNode node, int id){this.node = node;this.id = id;}}public int widthOfBinaryTree(TreeNode root) {if(root == null){return 0;}Deque<Pair> deq = new LinkedList<>();deq.offerLast(new Pair(root,1));int res = 0;while(!deq.isEmpty()){int len = deq.size();int low = 0, high = 0;for(int i = 0; i < len; i ++){Pair temp = deq.pollFirst();TreeNode cur = temp.node;int curId = temp.id;if(i == 0){low = curId;}if(i == len - 1){high = curId;}if(cur.left != null){deq.offerLast(new Pair(cur.left,curId*2));}if(cur.right != null){deq.offerLast(new Pair(cur.right,curId*2+1));}}res = Math.max(res,(high-low+1));}return res;}
}
DFS方式,采用一个List集合记录左侧第一个节点的id,使用depth和List集合的长度控制层数,当第一次进入某一层时,List的长度只能是depth-1才是第一个左孩子,左孩子一旦加入,List的长度就等于depth了,此时同一层的其他节点就不会加入集合了,那么遍使用其他节点,减去本层第一个左孩子,来更新本层宽度
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {List<Integer> list = new ArrayList<>();int res = 1;public int widthOfBinaryTree(TreeNode root) {if(root == null){return 0;} fun(root, 1, 1);return res;}public void fun(TreeNode root, int depth, int id){if(root == null){return;}if(depth - 1 == list.size()){list.add(id);}else{res = Math.max(res, id - list.get(depth-1) + 1);}fun(root.left, depth+1, id*2);fun(root.right, depth+1, id*2+1);}
}
相关文章:
力扣labuladong——一刷day43
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、力扣257. 二叉树的所有路径二、力扣129. 求根节点到叶节点数字之和三、力扣199. 二叉树的右视图四、力扣662. 二叉树最大宽度 前言 一般来说,如…...
MapApp 地图应用
1. 简述 1.1 重点 1)更好地理解 MVVM 架构 2)更轻松地使用 SwiftUI 框架、对齐、动画和转换 1.2 资源下载地址: Swiftful-Thinking:https://www.swiftful-thinking.com/downloads 1.3 项目结构图: 1.4 图片、颜色资源文件图: 1.5 启动图片配置图: 2. Mo…...
Java之反射获取和赋值字段
在Java中,反射能够使得代码更加通用,往往用于工具类中。 但常常我们在获取或者赋值反射的属性时,会出现没有赋值成功的结果,往往是由于这个属性在父级中而导致的,这个时候我们就不能用getDeclaredField方法单独获取字段…...
ckplayer自己定义风格播放器的开发记录
CKplayer是一款基于Flash和HTML5技术的开源视频播放器,支持多种格式的音视频播放,并且具有优秀的兼容性和扩展性。 它不仅可以在网页上播放本地或者网络上的视频,还可以通过代码嵌入到网页中,实现更加个性化的播放效果。CKplayer…...
全网最全Django面试题整理(一)
Django 中的 MTV 是什么意思? 在Django中,MTV指的是“Model-Template-View”,而不是常见的MVC(Model-View-Controller)架构。Django的设计理念是基于MTV的 Model(模型) 模型代表数据存取层&am…...
vue统一登录
说明: 统一登录其实就是前端去判断Url地址的token 之后如果有token未过期就直接跳转到首页。 说到浏览器输入url地址,那从浏览器输入地址一共发生了几件事大致如下: DNS解析域名,获取IP地址 --》 建立TCP连接(三次握…...
MVSNet论文笔记
MVSNet论文笔记 摘要1 引言2 相关基础2.1 多视图立体视觉重建(MVS Reconstruction)2.2 基于学习的立体视觉(Learned Stereo)2.3 基于学习的多视图的立体视觉(Learned MVS) 3 MVSNet3.1 网络架构3.2 提取图片…...
大型 APP 的性能优化思路
做客户端开发都基本都做过性能优化,比如提升自己所负责的业务的速度或流畅性,优化内存占用等等。但是大部分开发者所做的性能优化可能都是针对中小型 APP 的,大型 APP 的性能优化经验并不会太多,毕竟大型 APP 就只有那么几个&…...
K8S配置资源管理
这里写目录标题 K8S配置资源管理一.Secret1.介绍2.Secret 有四种类型3.创建 Secret4.使用方式 二.ConfigMap1.介绍2.创建 ConfigMap3.Pod 中使用 ConfigMap4.用 ConfigMap 设置命令行参数5.通过数据卷插件使用ConfigMap6.ConfigMap 的热更新7.ConfigMap 更新后滚动更新 Pod K8S…...
Redis 的集群模式实现高可用
来源:Redis高可用:武林秘籍存在集群里,那稳了~ (qq.com) 1. 引言 前面我们已经聊过 Redis 的主从同步(复制)和哨兵机制,这期我们来聊 Redis 的集群模式。 但是在超大规模的互联网应用中,业务规…...
21、嵌套路由实战操作
1、创建内嵌子路由,你需要添加一个vue文件,同时添加一个与该文件同名的目录用来存放子视图组件。 2、在父组件(.vue)内增加用于显示子视图内容 新建文件 pages\index_id.vue 生成的对应路由 {path: "/",component: _…...
WPF 控件的缩放和移动
WPF 控件的缩放和移动 1.页面代码 <ContentControl ClipToBounds"True" Cursor"SizeAll"><Viewboxx:Name"viewbox"MouseDown"viewbox_MouseDown"MouseMove"viewbox_MouseMove"MouseWheel"Viewbox_MouseWhee…...
Python and和or的优先级实例比较
Python and和or的优先级 and和or都是Python的逻辑运算符,都为保留字。通常情况下,在没有括号影响,and和or的优先级中and在代码的逻辑运算过程中会相对优先一些,及在同一行的Python代码中,and会优先与or执行。下面将通…...
数据结构与算法编程题2
逆置线性表,使空间复杂度为 O(1) #include <iostream> using namespace std;typedef int ElemType; #define Maxsize 100 #define OK 1 #define ERROR 0 typedef struct SqList {ElemType data[Maxsize];int length; }SqList;void Init_SqList(SqList& …...
Java开发者的Python快速进修指南:控制之if-else和循环技巧
简单介绍 在我们今天的学习中,让我们简要了解一下Python的控制流程。考虑到我们作为有着丰富Java开发经验的程序员,我们将跳过一些基础概念,如变量和数据类型。如果遇到不熟悉的内容,可以随时查阅文档。但在编写程序或逻辑时&…...
二进制部署k8s集群-过程中的问题总结(接上篇的部署)
1、kube-apiserver部署过程中的问题 kube-apiserver.conf配置文件更改 2、calico的下载地址 curl https://docs.projectcalico.org/v3.20/manifests/calico.yaml -O 这里如果kubernetes的节点服务器为多网卡配置会产生报错 修改calino.yaml配置文件 解决方法: 调…...
IOS 关于CoreText的笔记
放大 一.CoreText计算attributeString显示所占区域 百度搜索有三种方法: 1.方法 - (CGRect)boundingRectWithSize:(CGSize)size options:(NSStringDrawingOptions)options context:(nullable NSStringDrawingContext *)context 2.使用CTFrameRef 的 CTFrameGetLin…...
基础课6——开放领域对话系统架构
开放领域对话系统是指针对非特定领域或行业的对话系统,它可以与用户进行自由的对话,不受特定领域或行业的知识和规则的限制。开放领域对话系统需要具备更广泛的语言理解和生成能力,以便与用户进行自然、流畅的对话。 与垂直领域对话系统相比…...
Hive常见的面试题(十二道)
Hive 1. Hive SQL 的执行流程 ⾸先客户端通过shell或者Beeline等⽅式向Hive提交SQL语句,之后sql在driver中经过 解析器(SQL Parser):将 SQL 字符串转换成抽象语法树 AST,这一步一般都用第三方工具库完成,比如 ANTLR&…...
1688商品详情API跨境专用接口php java
一、引言 随着全球电子商务的快速发展,跨境电子商务已经成为一种重要的国际贸易形式。1688作为全球最大的B2B电子商务平台之一,不仅拥有大量的商品资源,还为商家提供了丰富的API接口,以实现更高效、更便捷的电子商务活动。其中&a…...
Intv_AI_MK11跨平台开发体验:在Windows WSL2中无缝使用GPU进行模型调试
Intv_AI_MK11跨平台开发体验:在Windows WSL2中无缝使用GPU进行模型调试 1. 为什么选择WSL2进行AI开发 对于习惯Windows系统的开发者来说,直接使用Linux环境进行AI模型开发往往面临诸多不便。WSL2(Windows Subsystem for Linux 2)…...
EPWM模块影子寄存器的加载机制与应用场景解析
1. EPWM模块影子寄存器基础概念 第一次接触EPWM模块的影子寄存器时,我也被这个"影子"的概念绕晕了。后来在实际项目中调试电机控制才发现,这个机制简直是PWM波形控制的"安全气囊"。简单来说,影子寄存器就是活动寄存器的&…...
基于python的演唱会抢票系统
目录同行可拿货,招校园代理 ,本人源头供货商核心功能模块技术实现要点扩展功能设计异常处理方案项目技术支持源码获取详细视频演示 :文章底部获取博主联系方式!同行可合作同行可拿货,招校园代理 ,本人源头供货商 核心功能模块 用户管理模块 注册/登录功…...
RTL8188EU USB WiFi模块AP模式配置避坑指南
RTL8188EU USB WiFi模块AP模式配置实战:从编译到避坑全解析 在物联网和嵌入式开发领域,RTL8188EU USB WiFi模块因其低成本和高兼容性被广泛使用。但当你尝试将其配置为AP模式时,官方hostapd的兼容性问题往往会让开发者陷入数天的调试泥潭。我…...
Phi-4-mini-reasoning:轻量级推理模型在人工智能浪潮中的定位
Phi-4-mini-reasoning:轻量级推理模型在人工智能浪潮中的定位 1. 轻量级推理模型的时代价值 当ChatGPT等千亿参数大模型占据媒体头条时,一个容易被忽视的趋势正在悄然兴起——轻量级推理模型正在特定领域展现出惊人的实用性。Phi-4-mini-reasoning正是…...
adb工具箱下载,免费的ADB工具箱,手机投屏工具等推荐
Android Debug Bridge(ADB,安卓调试桥)是 Google 推出的跨平台命令行工具,属 Android SDK 平台工具核心组件,用于电脑与安卓设备(手机、平板、模拟器)通信Android Developers。 它采用客户端 -…...
为什么选择Zabbix而不是Prometheus?K8s监控工具深度对比与实战配置
Zabbix与Prometheus在Kubernetes监控中的技术决策指南 当企业级容器平台需要构建监控体系时,技术选型往往成为困扰架构师的核心难题。作为当下最主流的两个开源监控解决方案,Zabbix与Prometheus在Kubernetes生态中的表现各有千秋。本文将基于实际生产环境…...
智能票务自动化工具:提升大型活动门票获取效率的全流程解决方案
智能票务自动化工具:提升大型活动门票获取效率的全流程解决方案 【免费下载链接】Automatic_ticket_purchase 大麦网抢票脚本 项目地址: https://gitcode.com/GitHub_Trending/au/Automatic_ticket_purchase 在数字化时代,大型展会、体育赛事等热…...
GPU算力高效利用:Pixel Language Portal在单卡多实例部署中的资源隔离与负载均衡教程
GPU算力高效利用:Pixel Language Portal在单卡多实例部署中的资源隔离与负载均衡教程 1. 引言:为什么需要单卡多实例部署 在AI应用开发中,GPU资源往往是稀缺且昂贵的。Pixel Language Portal作为一款基于Tencent Hunyuan-MT-7B的高端翻译工…...
