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

力扣hot100:199. 二叉树的右视图/437. 路径总和 III(dfs/回溯/树上前缀和/哈希表)

文章目录

  • 一、LeetCode:199. 二叉树的右视图
  • 二、LeetCode:437. 路径总和 III

一、LeetCode:199. 二叉树的右视图

LeetCode:199. 二叉树的右视图
在这里插入图片描述
差点因为是个中等题打退堂鼓。其实比较简单。
右视图实际上只需要找到,每一层的最右边的那个结点即可。
dfs

  • 确保每次找到底层最右边的结点,时间复杂度 O ( n ) O(n) O(n)
class Solution {
public:vector<int> rightSideView(TreeNode* root) {cur_floor = 0;rightNode(root,0);return ans;}
private:void rightNode(TreeNode * root,int floor){//找到当前层最靠右的结点if(!root) return;if(floor == cur_floor){ans.emplace_back(root->val);cur_floor++;}rightNode(root->right,floor + 1);rightNode(root->left, floor + 1);return;}int cur_floor;vector<int> ans;
};

实际上使用层序遍历更好理解,每次选择一层的最后一个节点就行!


二、LeetCode:437. 路径总和 III

LeetCode:437. 路径总和 III
在这里插入图片描述
这个问题使用dfs可以解决,不过实现起来比较复杂,时间复杂度是 O ( n 2 ) O(n^2) O(n2)。我们先考虑其他方法。

发现使用树上前缀和很容易解决,最坏时间复杂度也是 O ( n 2 ) O(n^2) O(n2),所以我们先考虑使用前缀和。
未优化的前缀和+dfs回溯

  • 最坏时间复杂度是 O ( n 2 ) O(n^2) O(n2)
  • 前缀和求和,需要考虑元素大小的问题,所以要使用long long
  • 对于每一个结点需要求其前缀和,以及以当前结点结尾的序列的值的总和是否存在等于targetSum
  • 向下递归左右子节点,向上回溯。

在这里插入图片描述

class Solution {
public:int pathSum(TreeNode* root, int targetSum) {if(!root) return 0;vector<long long> presum;presum.emplace_back(0);//导入前导0getNum(root,targetSum,presum);return Num;}
private:void getNum(TreeNode * root,int targetSum,vector<long long> & presum){if(!root) return;//压入当前值的前缀和presum.emplace_back(root->val + presum.back());//判断以当前结点结尾的序列是否存在targetSum,由于存在负值,因此无法提前breakfor(int i = presum.size() - 2;i >= 0;--i){if(presum.back() - presum.at(i) == targetSum){++Num;}}//继续向下递归getNum(root->left,targetSum,presum);getNum(root->right,targetSum,presum);//弹出当前值回溯presum.pop_back();return;}int Num=0;
};

做过两数之和之后很容易想到使用哈希表直接查找使用存在所需要的值。

  • p r e s u m 1 − p r e s u m 2 = t a r g e t S u m presum1 - presum2 = targetSum presum1presum2=targetSum
  • p r e s u m 2 = p r e s u m 1 − t a r g e t S u m presum2 = presum1 - targetSum presum2=presum1targetSum

我们真的是需要哈希表找到需要的值吗?在这里我们只需要之前有多少个这样的值就行了!
因此哈希的key = 目标前缀和,value = 目标前缀和的个数

使用哈希优化的前缀和+dfs回溯

  • 哈希查找,每个结点查找一次,平均时间复杂度 O ( 1 ) O(1) O(1),整个时间复杂度为 O ( n ) O(n) O(n)
  • 使用std::unordered_map的count方法,返回值是01表示存在或不存在。
  • 必须先判断是否存在所需前缀和,再压入当前值。 原因是当前值和所需前缀和可能刚好相等,导致当前前缀和也变成了答案的一部分,但实际上它不能是答案的一部分相当于之前所说的是同一个前缀和了,这使得序列为空。

在这里插入图片描述

class Solution {
public:int pathSum(TreeNode* root, int target) {if(!root) return 0;targetSum = target;presum_num[0] = 1;//导入前导0getNum(root,0);return Num;}
private:void getNum(TreeNode * root,long long presum){if(!root) return;long long cur_presum = presum + root->val;//判断以当前结点结尾的序列是否存在targetSumif(presum_num.count(cur_presum - targetSum) != 0)Num += presum_num[cur_presum - targetSum];//压入当前值的前缀和presum_num[cur_presum]++;//继续向下递归getNum(root->left,cur_presum);getNum(root->right,cur_presum);//弹出当前值回溯if(presum_num[cur_presum] != 1) presum_num[cur_presum]--;else presum_num.erase(cur_presum);return;}int Num=0;int targetSum;unordered_map<long long,int> presum_num;
};

前缀和的方法如果之前接触过很容易想到,不过这里建议学习深度优先遍历的方法,更深入理解dfs。
dfs

  • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
  • 实现两个递归函数:
    • 第一个函数dfs:以根结点开始向下求和,得到targetSumNum++
    • 第二个函数getNum:遍历所有树节点,每个结点调用dfs函数。

在这里插入图片描述

class Solution {
public:int pathSum(TreeNode* root, int target) {targetSum = target;getNum(root);return Num;}
private:void getNum(TreeNode * root){if(!root) return;dfs(root,0);//包含本结点向下递归getNum(root->left);getNum(root->right);return;}void dfs(TreeNode * root,long long sum){if(!root) return;if(root->val + sum == targetSum) Num++;dfs(root->left,sum + root->val);dfs(root->right,sum + root->val);return;}int Num = 0;int targetSum;
};

相关文章:

力扣hot100:199. 二叉树的右视图/437. 路径总和 III(dfs/回溯/树上前缀和/哈希表)

文章目录 一、LeetCode&#xff1a;199. 二叉树的右视图二、LeetCode&#xff1a;437. 路径总和 III 一、LeetCode&#xff1a;199. 二叉树的右视图 LeetCode&#xff1a;199. 二叉树的右视图 差点因为是个中等题打退堂鼓。其实比较简单。 右视图实际上只需要找到&#xff0c…...

浅谈 HTTPS

文章目录 HTTPS 简介HTTPS 特点HTTPS 缺点与 HTTP 的区别HTTPS 工作流程1. 服务端生成密钥对2. 服务端申请数字证书3. 服务端发送数字证书4. 客户端验证数字证书5. 客户端解析证书内容6. 客户端传送加密信息7. 服务端解密信息8. 双方协商生成会话密钥并交换9. 使用会话密钥进行…...

js手动实现unshift

js 手动实现数组的unshift unshift是什么&#xff1f; unshift() 方法可向数组的开头添加一个或更多元素&#xff0c;并返回新的长度。 注意&#xff1a; 该方法将改变数组的数目。 语法&#xff1a; array.unshift(item1,item2, ..., itemX)代码实现 首先&#xff0c;在…...

Failed to get DISPLAY: Error: All configured authentication methods failed 解决方法

Vscode一连接远程服务器就报错&#xff1a; 这个时候我们是无法使用Xming显示图像的。 尝试后发现&#xff0c;Windows电脑能够ping通服务器ip&#xff0c;但是服务器ping不通Windows电脑&#xff1a; 在网上查攻略&#xff0c;设置Windows电脑ip地址白名单&#xff0c;但…...

随便聊一下 显控科技 控制屏 通过 RS485 接口 上位机 通讯 说明

系统搭建&#xff1a; 1、自己研发的一个小系统&#xff08;采集信号&#xff0c;将采集的信号数字化&#xff09;通过COM口&#xff0c;连接显控屏 COM3 口采用 485 协议送到显控屏&#xff08;显控科技&#xff09;的显示屏展示出来&#xff09;。 2、显控屏 将 展示的数据…...

C++学习笔记(多线程)

Multithreading 1、线程的基本操作1.1、创建线程1.2、等待线程和分离线程1.3、获取线程id 2、互斥锁3、条件变量4、例程 1、线程的基本操作 从C11开始推出关于多线程的库和函数&#xff0c;相比于Linux所配套的资源&#xff0c;C11提供的函数更加容易理解和操作&#xff0c;对…...

解决Redis的键值前出现类似\xAC\xED\x00\x05t\x00*这样的字符序列

文章目录 1.问题2.解决方法3.StringRedisTemplate和RedisTemplate的区别 1.问题 在使用RedisTemplate对Redis进行操作时,发现Reids键值对前有\xAC\xED\x00\x05t\x00*这样的字符序列 如图所示: 虽说不影响使用,但是听影响观感的 2.解决方法 查找了很多方法,可以指定RedisTem…...

分享 Kamailio 5.7.x 预处理一例

来自工单&#xff0c;很不错 不翻译了&#xff0c;认真看的话都能看懂 #!define IPADDR 127.0.0.1 #!defexp SIPURI "sip:" IPADDR ":5060" #!defexp QSIPURI "sip: IPADDR :5060" #!defexp V16 1<<4 Another possibility is using…...

学QT的第三天~

ikun登录界面完善 #include "mywidget.h" void MyWidget::bth1() { if(edit3 ->text()"520cxk"&&edit4 ->text()"1314520") { //1.实例化一个QmessageBox类的对象 QMessageBox box(QMessageBox::Information, //图标 "恭喜…...

数据结构---时间复杂度+空间复杂度

算法(algorithm)简单说就是解决问题的方法。方法有好坏&#xff0c;同样算法也是&#xff0c;有效率高的算法&#xff0c;也有效率低的算法。衡量算法的好坏一般从时间和空间两个维度衡量&#xff0c;也就是本文要介绍的时间复杂度和空间复杂度。有些时候&#xff0c;时间与空间…...

Verilog 触发器状态机语言描述

触发器状态机语言描述 触发器状态机语言用于描述映射到 ILA 调试核的高级触发器逻辑的复杂触发条件。触发器状态机具有下列特性 &#xff1a; • 最多 16 种状态。 • 用于复杂状态转换的单向、双向和三向条件分支。 • 4 个内置 16 位计数器 &#xff0c; 用于对事件…...

等保保护测评试题中

二、多选题 1、防火墙提供的接入模式中包括&#xff08;ABCD&#xff09; A.网关模式 B.透明模式 C.混合模式 D.旁路接入模式 2、不同设VLAN之间要进行通信&#xff0c;可以通过 .&#xff08;AB&#xff09; A.交换机 B.路由器 C.网闸 D.入侵检测 E.入侵防御系统…...

SD-Turbo部署

stabilityai/sd-turbo 官网 2023 年 11 月 30 日 继推出 SDXL-Turbo 之后&#xff0c;我们又发布了SD-Turbo。 2023 年 11 月 28 日 我们正在发布 SDXL-Turbo&#xff0c;一种闪电般快速的文本到图像模型。除了模型之外&#xff0c;我们还发布了技术报告 用法&#xff1…...

【ZZULIOJ】1095: 时间间隔(函数专题)(Java)

目录 题目描述 输入 输出 样例输入 Copy 样例输出 Copy 提示 code 题目描述 从键盘输入两个时间点(24小时制&#xff09;&#xff0c;输出两个时间点之间的时间间隔&#xff0c;时间间隔用“小时:分钟:秒”表示。要求程序定义如下两个函数&#xff0c;并在main()中调用…...

Rust:文件 launch.json 有什么用?

launch.json 是 Visual Studio Code&#xff08;VSCode&#xff09;中的一个配置文件&#xff0c;主要用于配置调试器。当你在 VSCode 中进行代码调试时&#xff0c;launch.json 文件告诉调试器如何启动和配置你的程序。 具体来说&#xff0c;launch.json 文件包含了以下信息&…...

vue3实现文字垂直滚动

在Vue 3中实现文字的垂直滚动&#xff0c;你可以使用CSS动画或者JavaScript来控制滚动行为。以下是一个简单的Vue 3组件示例&#xff0c;该组件使用CSS的keyframes动画来实现文字的垂直滚动效果&#xff1a; <template> <div class"vertical-scroll-text"&…...

Android4.4真机移植过程笔记(三)

如果文章字体看得不是很清楚&#xff0c;大家可以下载pdf文档查看&#xff0c;文档已上传&#xff5e;oo&#xff5e; 7、安装加密APK 需要修改文件如下&#xff1a; 相对Android4.2改动还是蛮大的&#xff0c;有些文件连路径都变了: //Android4.2 1、frameworks/native/libs…...

PostgreSQL备份恢复与复制

前言 随着国家战略层面对信息安全关注度越来越高&#xff0c;数据库是基础软件国产化自主可控的重要方面之一。PG是世界上最流行的开源关系型数据库之一&#xff0c;并且他是类BSD开源许可&#xff0c;开源协议非常友好&#xff0c;可以随意分发、闭源和开源&#xff0c;可以用…...

spring高级篇(八)

本篇对Spring MVC 的执行流程做一个简单总结 MVC执行流程总结 当浏览器发送一个请求&#xff0c;例如http://localhost:8080/hello&#xff0c;请求到达服务器后&#xff0c;一般会进行如下操作&#xff1a; 1、首先会经过DispatcherServlet&#xff0c;默认映射路径为 /&…...

UP互助 帮助UP起号做视频 支持B站和抖音

【软件名字】&#xff1a;UP互助 【软件版本】&#xff1a;1.0 【软件大小】&#xff1a;17.5MB 【软件平台】&#xff1a;安卓 【测试机型】&#xff1a;小米9 1.随便登个邮箱&#xff0c;添加自己平台的频道&#xff0c;然后就可以帮助别人&#xff0c;添加频道后在添加…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

Spring Boot + MyBatis 集成支付宝支付流程

Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例&#xff08;电脑网站支付&#xff09; 1. 添加依赖 <!…...

高抗扰度汽车光耦合器的特性

晶台光电推出的125℃光耦合器系列产品&#xff08;包括KL357NU、KL3H7U和KL817U&#xff09;&#xff0c;专为高温环境下的汽车应用设计&#xff0c;具备以下核心优势和技术特点&#xff1a; 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计&#xff0c;确保在…...

Win系统权限提升篇UAC绕过DLL劫持未引号路径可控服务全检项目

应用场景&#xff1a; 1、常规某个机器被钓鱼后门攻击后&#xff0c;我们需要做更高权限操作或权限维持等。 2、内网域中某个机器被钓鱼后门攻击后&#xff0c;我们需要对后续内网域做安全测试。 #Win10&11-BypassUAC自动提权-MSF&UACME 为了远程执行目标的exe或者b…...

RushDB开源程序 是现代应用程序和 AI 的即时数据库。建立在 Neo4j 之上

一、软件介绍 文末提供程序和源码下载 RushDB 改变了您处理图形数据的方式 — 不需要 Schema&#xff0c;不需要复杂的查询&#xff0c;只需推送数据即可。 二、Key Features ✨ 主要特点 Instant Setup: Be productive in seconds, not days 即时设置 &#xff1a;在几秒钟…...

虚拟机网络不通的问题(这里以win10的问题为主,模式NAT)

当我们网关配置好了&#xff0c;DNS也配置好了&#xff0c;最后在虚拟机里还是无法访问百度的网址。 第一种情况&#xff1a; 我们先考虑一下&#xff0c;网关的IP是否和虚拟机编辑器里的IP一样不&#xff0c;如果不一样需要更改一下&#xff0c;因为我们访问百度需要从物理机…...