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

【递归】【回溯】Leetcode 112. 路径总和 113. 路径总和 II

【递归】【回溯】Leetcode 112. 路径总和 113. 路径总和 II

  • 112. 路径总和
    • 解法:递归 有递归就有回溯 记得return正确的返回上去
  • 113. 路径总和 II
    • 解法 递归

如果需要搜索整棵二叉树,那么递归函数就不要返回值
如果要搜索其中一条符合条件的路径,递归函数就需要返回值,因为遇到符合条件的路径了就要及时返回

112. 路径总和

---------------🎈🎈题目链接🎈🎈-------------------
在这里插入图片描述

解法:递归 有递归就有回溯 记得return正确的返回上去

count初始等于targetsum,逐次减,如果到了叶子结点正好count为0,那么就返回true
终止条件:if(root.left = null && root.right = null && count=0){ return true; }

时间复杂度O(N)
空间复杂度O(N)

/*** 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 {public boolean hasPathSum(TreeNode root, int targetSum) {// 终止条件if(root == null) return false;int count = targetSum-root.val;return help(root,count);}public boolean help(TreeNode root, int count){if(root.left==null && root.right==null && count==0){return true;}if(root.left==null && root.right==null && count!=0){return false;}// 左if(root.left != null){if(help(root.left, count-root.left.val)){return true;}}// 右if(root.right != null){if(help(root.right, count-root.right.val)){return true;}}return false;}}

113. 路径总和 II

---------------🎈🎈题目链接🎈🎈-------------------
在这里插入图片描述

解法 递归

时间复杂度O(N)
空间复杂度O(N)

/*** 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<List<Integer>> finalresult = new ArrayList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<Integer> result = new ArrayList<>();if(root == null) return finalresult;result.add(root.val);helper(root,targetSum-root.val,result);return finalresult;}public void helper(TreeNode root, int count, List<Integer> result){if(root.left == null && root.right==null && count==0){finalresult.add(new ArrayList<>(result)); // 这里千万不能finalresult.add(result) 这就成了添加result的引用,每次都会变}// 左if(root.left != null){result.add(root.left.val);helper(root.left, count-root.left.val,result);result.remove(result.size()-1); // 回溯}// 右if(root.right != null){result.add(root.right.val);helper(root.right,count-root.right.val,result);result.remove(result.size()-1); // 回溯}}
}

相关文章:

【递归】【回溯】Leetcode 112. 路径总和 113. 路径总和 II

【递归】【回溯】Leetcode 112. 路径总和 113. 路径总和 II 112. 路径总和解法&#xff1a;递归 有递归就有回溯 记得return正确的返回上去 113. 路径总和 II解法 递归 如果需要搜索整棵二叉树&#xff0c;那么递归函数就不要返回值 如果要搜索其中一条符合条件的路径&#xff…...

AxureCloud配置文件详细介绍

AxureCloud配置文件详细介绍 原文地址&#xff1a;https://docs.axure.com/axure-cloud/business/custom-settings-json/ 通过修改 customsettings.json 可以修改AxureCloud私有部署的域名、端口、HTTPS、存储目录、是否开启插件等, 默认安装的路径为: C:\Program Files\Axure…...

Centos开机网卡自启动失败

问题背景 每次都要手动启动在这里插入代码片 解决方案: 关闭 NetworkManager 服务 systemctl disable NetworkManager systemctl stop NetworkManager重启就会发现网卡已经可以自动启动了...

华为OD技术面试案例3-2024年

技术一面&#xff1a; 1.手撕代码&#xff0c;算法题&#xff1a; 【最小路径和】 手撕代码通过&#xff0c;面试官拍了照片 2.深挖项目&#xff0c;做过的自认为最好的一个项目&#xff0c;描述做过的项目的工作过程&#xff0c;使用到哪些技术&#xff1f; 技术二面&…...

全面升级!Apache HugeGraph 1.2.0版本发布

图数据库以独特的数据管理和分析能力&#xff0c;在企业数智化转型的过程中正在成为数据治理的核心&#xff0c;根据IDC调研显示&#xff0c;95%的企业认为图数据库是重要的数据管理工具&#xff0c;超过65%的厂商认为在业务上图数据库优于其他选择&#xff0c;尤其是在金融风控…...

WinCC如何与三菱Q系列PLC进行以太网通讯

本文主要描述人机界面WinCC如何与三菱Q系列PLC进行以太网通讯&#xff0c;主要介绍了CPU自带以太网口和扩展以太网模块两种情况以及分别使用TCP、UDP两种协议进行通讯组态步骤及其注意事项。 一、 说明 WinCC从V7.0 SP2版本开始增加了三菱以太网驱动程序&#xff0c;支持和三…...

Spring11、整合Mybatis

11、整合Mybatis 步骤&#xff1a; 导入相关jar包 junit <dependency><groupId>junit</groupId><artifactId>junit</artifactId><version>4.12</version> </dependency> mybatis <dependency><groupId>org.my…...

C语言练习:(力扣645)错误的集合

题目链接&#xff1a;645. 错误的集合 - 力扣&#xff08;LeetCode&#xff09; 集合 s 包含从 1 到 n 的整数。不幸的是&#xff0c;因为数据错误&#xff0c;导致集合里面某一个数字复制了成了集合里面的另外一个数字的值&#xff0c;导致集合 丢失了一个数字 并且 有一个数字…...

广和通发布基于MediaTek T300平台的RedCap模组FM330系列及解决方案

世界移动通信大会MWC 2024期间&#xff0c;广和通发布基于MediaTek T300平台的RedCap模组FM330系列&#xff0c;加速5G-A繁荣发展。FM330系列及其解决方案采用全球先进RedCap方案&#xff0c;满足移动宽带和工业互联对高能效的需求。 广和通FM330系列采用全球首款6nm制程且集成…...

代码随想录训练营第六十三天打卡|503.下一个更大元素II 42. 接雨水

503.下一个更大元素II 1.暴力法&#xff0c;和每日温度那一题如出一辙&#xff0c;循环数组用了一个取模运算就解决了。 class Solution { public:vector<int> nextGreaterElements(vector<int>& nums) {int n nums.size();vector<int> result;for (i…...

【web】nginx+php环境搭建-关键点(简版)

一、nginx和php常用命令 命令功能Nginxphp-fpm启动systemctl start nginxsystemctl start php-fpm停止systemctl stop nginxsystemctl stop php-fpm重启systemctl restart nginxsystemctl restart php-fpm查看启动状态systemctl status nginxsystemctl status php-fpm开机自启…...

1、什么是ETF?

ETF是Exchange Traded Fund的英文缩写&#xff0c;中文称为“交易型开放式指数基金”&#xff0c;又称“指数股”。ETF是一种指数投资工具&#xff0c;通过复制标的指数来构建跟踪指数变化的组合证券&#xff0c;使得投资者通过买卖一种产品就实现了一揽子证券的交易。简单来说…...

备战蓝桥杯Day18 - 双链表

一、每日一题 蓝桥杯真题之工作时长 这个题写代码做的话很麻烦&#xff0c;而且我也不一定能写出来&#xff0c;所以我直接就是用的excel来计算的时间和。 使用excel的做法 1.先把文件中的时间复制到excel中。 2.把日期和时间分到两列。 分成两列的步骤&#xff1a; 选中要…...

【大数据】Flink 内存管理(二):JobManager 内存分配(含实际计算案例)

《Flink 内存管理》系列&#xff08;已完结&#xff09;&#xff0c;共包含以下 4 篇文章&#xff1a; Flink 内存管理&#xff08;一&#xff09;&#xff1a;设置 Flink 进程内存Flink 内存管理&#xff08;二&#xff09;&#xff1a;JobManager 内存分配&#xff08;含实际…...

(2024,Sora 逆向工程,DiT,LVM 技术综述)Sora:大视觉模型的背景、技术、局限性和机遇回顾

Sora: A Review on Background, Technology, Limitations, and Opportunities of Large Vision Models 公和众和号&#xff1a;EDPJ&#xff08;进 Q 交流群&#xff1a;922230617 或加 VX&#xff1a;CV_EDPJ 进 V 交流群&#xff09; 目录 0. 摘要 1. 简介 2. 背景 2.1…...

MySQL基础(二)

文章目录 MySQL基础&#xff08;二&#xff09;1. 数据库操作-DQL1.1 介绍1.2 语法1.3 基本查询1.4 条件查询1.5 聚合函数1.6 分组查询1.7 排序查询1.8 分页查询1.9 案例1.9.1 案例一1.9.2 案例二 2. 多表设计2.1 一对多2.1.1 表设计2.1.2 外键约束 2.2 一对一2.3 多对多2.4 案…...

el-table 多选表格存在分页,编辑再次操作勾选会丢失原来选中的数据

el-table表格多选时&#xff0c;只需要添加type"selection"&#xff0c; row-key及selection-change&#xff0c;如果存在分页时需要加上reserve-selection&#xff0c;这里就不写具体的实现方法了&#xff0c;可以查看我之前的文章&#xff0c;这篇文章主要说一下存…...

备战蓝桥杯————如何判断回文链表

如何判断回文链表 题目描述 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true示例 2&#xff1a;…...

linux 文本编辑命令【重点】

目录 vi&vim介绍 vim安装 vim使用 查找命令 find grep 文本编辑的命令&#xff0c;主要包含两个: vi 和 vim vi&vim介绍 作用: vi命令是Linux系统提供的一个文本编辑工具&#xff0c;可以对文件内容进行编辑&#xff0c;类似于Windows中的记事本 语法: vi file…...

C#面:ref 和 out 的区别

ref 关键字&#xff1a; 在使用 ref 关键字时&#xff0c;传递的参数必须在方法调用之前进行初始化。在方法内部&#xff0c;对 ref 参数的任何修改都会影响到原始变量。ref 参数在方法内部和外部都必须具有相同的类型。 out 关键字 out 参数在方法内部必须被赋值。在使用 ou…...

HTTPoison与JSON处理:如何高效集成Jason库进行数据序列化

HTTPoison与JSON处理&#xff1a;如何高效集成Jason库进行数据序列化 【免费下载链接】httpoison Yet Another HTTP client for Elixir powered by hackney 项目地址: https://gitcode.com/gh_mirrors/ht/httpoison HTTPoison是Elixir生态中一款功能强大的HTTP客户端&am…...

2026.4.19

大概在2024年开始&#xff0c;我尝试了写下东西表达&#xff0c;因为我实在不知道该如何写作&#xff0c;从小学的是应考的八股&#xff0c;“写作”对于我而言是模糊的概念。我甚至从网络/社交平台开始写留言开始&#xff0c;我意识到如果你的表达不够准确&#xff0c;你就要被…...

省钱攻略:在AutoDL上用网盘离线安装PyTorch和Transformers,避开pip超时

AutoDL云平台深度学习环境搭建&#xff1a;网盘离线安装PyTorch全攻略 在按小时计费的云GPU平台上&#xff0c;每一分钟都在消耗真金白银。最近帮团队优化AutoDL环境搭建流程时发现&#xff0c;90%的实例启动时间浪费在pip安装环节——网络波动导致重复下载、依赖冲突引发环境崩…...

解锁BoTorch:PyTorch生态中的贝叶斯优化利器

解锁BoTorch&#xff1a;PyTorch生态中的贝叶斯优化利器 【免费下载链接】botorch Bayesian optimization in PyTorch 项目地址: https://gitcode.com/gh_mirrors/bo/botorch BoTorch是PyTorch生态中一款强大的贝叶斯优化工具&#xff0c;它能够帮助开发者在复杂的高维空…...

串口驱动开发:从内核源码到调试坑位全解析

昨天深夜调试现场&#xff0c;设备管理器里能看到ttyS0&#xff0c;但cat /dev/ttyS0就是没数据。示波器测TX脚明明有波形&#xff0c;minicom里却一片死寂。这种“硬件有信号&#xff0c;软件没反应”的尴尬&#xff0c;十有八九是串口驱动配置出了问题。今天咱们就深挖Linux串…...

【AGI环境监测革命】:3大颠覆性应用、7类实时预警场景与2025碳中和落地路径

第一章&#xff1a;AGI驱动的环境监测范式跃迁 2026奇点智能技术大会(https://ml-summit.org) 传统环境监测长期受限于传感器密度、数据孤岛与响应滞后性&#xff0c;而具备自主推理、多模态融合与跨域协同能力的通用人工智能&#xff08;AGI&#xff09;正从根本上重构这一技…...

TypeScript的template literal types实现SQL查询的类型安全

在现代Web开发中&#xff0c;TypeScript因其强大的类型系统而备受青睐。数据库操作中的SQL查询仍然是一个容易出错的领域&#xff0c;尤其是拼接字符串时容易引发SQL注入或字段名错误。TypeScript 4.1引入的template literal types为解决这一问题提供了新思路&#xff0c;它允许…...

从零训练一个小模型-nanoGPT 模型训练 (一)数据预处理

最近在学习模型训练&#xff0c;实际上在大模型训练上&#xff0c;我并没有深厚的背景&#xff0c;通过视频课程和b站上的一些分享&#xff0c;开始入门。 由于我非神经网络这些相关的专业&#xff0c;所以想把自己学习的过程和经验总结记录下来&#xff0c;一方面自己可以巩固…...

LeetCodeHot100 2. 两数相加 思路JavaScript版本代码

题目思路以题目提供的例子为例来进行思考分别将两个数倒过来计算&#xff0c;类似如图,结合链表其实非常方便。创建一个新的虚拟链表newlist存储计算结果&#xff0c;tail指向该链表的末尾。首先计算l1和l2的首位&#xff0c;25 7&#xff0c;更新newlist的tail的值为7&#x…...

尝试 Gemini CLI 替代Claude,Jeecg skills基本通畅,但遇致命问题

AI Agent 使用体验 | JeecgBoot 团队将日常 Claude Code 工作流迁移到 Gemini CLI 的阶段性总结为什么要换 Gemini CLI JeecgBoot 低代码团队平时主力用 Claude Code 做代码生成、文档写作、重构脚本。但 Claude 最近实名认证 频繁封号的事闹得人心惶惶——身边已经有好几个账…...