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

【算法刷题 | 二叉树 06】4.10( 路径总和、路径总和 || )

在这里插入图片描述

文章目录

  • 13.路径总和
    • 13.1问题
    • 13.2解法一:递归
      • 13.2.1递归思路
        • (1)确定递归函数参数以及返回值
        • (2)确定终止条件
        • (3)确定递归逻辑
      • 13.2.2代码实现
  • 14.路径总和 ||
    • 14.1问题
    • 14.2解法一:递归
      • 14.2.1递归思路
        • (1)确定递归函数参数以及返回值
        • (2)确定终止条件
        • (3)确定递归逻辑
      • 14.2.2代码实现

13.路径总和

13.1问题

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false

叶子节点 是指没有子节点的节点。

  • 示例一:

img

输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。

13.2解法一:递归

13.2.1递归思路

(1)确定递归函数参数以及返回值
  • 参数:节点、计数器(记录从根节点到该节点的值)、targetSum
  • 返回值:需要搜索整棵二叉树并且需要处理递归返回值的递归函数就需要返回值,此题使用boolean代表这颗树是否存在路径总和为targetSum的路径
private boolean traversal(TreeNode node,int count,int targetSum)
(2)确定终止条件
  • 当当前节点为叶子节点并且count=targetSum时,返回true(该count已经包含当前节点的值了);
  • 当当前节点为叶子节点,直接返回false
if(node.left==null && node.right==null && count==targetSum){return true;
}
if(node.left==null && node.right==null){return false;
}
(3)确定递归逻辑
  • 因为终止条件是判断叶子节点,所以递归的过程中就不要让空节点进入递归了;
  • 若该节点的左右孩子非空,则递归(注意递归函数的count加上左右孩子的值);
  • 递归完若发现为true,则直接返回true,否则进行回溯,不要该左孩子节点(count减去该值),进行右孩子节点的查找(回溯);
if(node.left!=null){if(traversal(node.left,count+=node.left.val,targetSum)){return true;}//回溯count-=node.left.val;
}
if(node.right!=null){if(traversal(node.right,count+=node.right.val,targetSum)){return true;1}//回溯count-=node.right.val;
}
return false;

13.2.2代码实现

public boolean hasPathSum(TreeNode root, int targetSum) {if(root==null){return false;}return traversal(root,root.val,targetSum);}private boolean traversal(TreeNode node,int count,int targetSum){if(node.left==null && node.right==null && count==targetSum){return true;}if(node.left==null && node.right==null){return false;}if(node.left!=null){if(traversal(node.left,count+=node.left.val,targetSum)){return true;}//回溯count-=node.left.val;}if(node.right!=null){if(traversal(node.right,count+=node.right.val,targetSum)){return true;}//回溯count-=node.right.val;}return false;}
}

14.路径总和 ||

14.1问题

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和 的路径

叶子节点 是指没有子节点的节点。

  • 示例一:

img

输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]

14.2解法一:递归

14.2.1递归思路

(1)确定递归函数参数以及返回值
  • 参数说明:
    • 求根节点到 node 节点的路径之和 == targetSum
    • paths存放当前路径
    • res存放符合路径总和为targetSum的路径
    • count代表从根节点到该节点的路径中和
  • 无返回值
private void traversal(TreeNode node, List<Integer> paths, List<List<Integer>> res, int count, int targetSum)
(2)确定终止条件
  • 若该节点为叶子节点,则判断count==targetSum,符合则添加该paths到res中,否则返回
if(node.left==null && node.right==null){if(count==targetSum)    {res.add(new ArrayList<>(path));}return;
}
(3)确定递归逻辑
if(node.left!=null){paths.add(node.left.val);traversal(node.left,paths,res,count+=node.left.val,targetSum);//回溯paths.remove(paths.size()-1);count-=node.left.val;
}if(node.right!=null){paths.add(node.right.val);traversal(node.right,paths,res,count+=node.right.val,targetSum);//回溯paths.remove(paths.size()-1);count-=node.right.val;
}

14.2.2代码实现

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {int count=0;List<List<Integer>> res=new ArrayList<>();List<Integer> paths=new ArrayList<>();if(root==null){return res;}paths.add(root.val);traversal(root,paths,res,count+=root.val,targetSum);return res;}private void traversal(TreeNode node, List<Integer> paths, List<List<Integer>> res, int count, int targetSum){if(node.left==null && node.right==null){if(count==targetSum){res.add(new ArrayList<>(paths));}return;}if(node.left!=null){paths.add(node.left.val);traversal(node.left,paths,res,count+=node.left.val,targetSum);//回溯paths.remove(paths.size()-1);count-=node.left.val;}if(node.right!=null){paths.add(node.right.val);traversal(node.right,paths,res,count+=node.right.val,targetSum);//回溯paths.remove(paths.size()-1);count-=node.right.val;}}
}

在这里插入图片描述

相关文章:

【算法刷题 | 二叉树 06】4.10( 路径总和、路径总和 || )

文章目录 13.路径总和13.1问题13.2解法一&#xff1a;递归13.2.1递归思路&#xff08;1&#xff09;确定递归函数参数以及返回值&#xff08;2&#xff09;确定终止条件&#xff08;3&#xff09;确定递归逻辑 13.2.2代码实现 14.路径总和 ||14.1问题14.2解法一&#xff1a;递归…...

代码学习记录37----动态规划

随想录日记part37 t i m e &#xff1a; time&#xff1a; time&#xff1a; 2024.04.06 主要内容&#xff1a;今天开始要学习动态规划的相关知识了&#xff0c;今天的内容主要涉及四个方面&#xff1a; 完全背包&#xff1b;零钱兑换 II &#xff1b;组合总和 Ⅳ 和单词拆分 …...

Spring Boot:Web开发之三大组件的整合

Spring Boot 前言Spring Boot 整合 ServletSpring Boot 整合 FilterSpring Boot 整合 Listener前言 在 Web 开发中,Servlet 、Filter 和 Listener 是 Java Web 应用中的三大组件。Servlet 是 Java 代码,通过 Java 的 API 动态的向客户端输出内容。Filter 是处于客户端与服务…...

2024.3.15力扣每日一题——卖木头块

2024.3.15 题目来源我的题解方法一 记忆化搜索&#xff08;自顶向下&#xff09;方法二 动态规划&#xff08;自底向上&#xff09; 题目来源 力扣每日一题&#xff1b;题序&#xff1a;2312 我的题解 方法一 记忆化搜索&#xff08;自顶向下&#xff09; 用 f(x,y)表示当木…...

vue快速入门(七)内联语句

注释很详细&#xff0c;直接上代码 上一篇 新增内容 button点击事件绑定内联语句写法与要求 源码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-wid…...

Docker实战教程 第2章 Docker基础

3-1 Docker介绍 什么是Docker 虚拟化&#xff0c;容器 Docker 是一个开源的应用容器引擎&#xff0c;基于 Go 语言 并遵从Apache2.0协议开源。 Docker 可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中&#xff0c;然后发布到任何流行的 Linux 机器上&…...

【S32K3 MCAL配置】-3.2-CANFD配置-发送“经典CAN/CANFD标准帧“和“经典CAN/CANFD扩展帧“(基于MCAL+FreeRTOS)

"><--返回「Autosar_MCAL高阶配置」专栏主页--> 目录 实现的架构:基于MCAL层 前期准备工作: 1 评估板S32K312EVB-Q172中CAN外设...

【airtest】自动化入门教程(四)Poco元素定位

目录 一、基础操作 1、通过属性名等方式 2、通过属性组合 3、子节点方式 4、子节点加属性组合方式 5、孙节点offspring 6、兄弟节点sibling 7、父节点parent 8、正则表达式 9、直到某个元素出现 10、直到某个元素消失 二、通过局部坐标定位 1、使用局部坐标系的cli…...

Go语言中如何处理goroutine和循环变量

对goroutine和循环变量处理不当可能是Go开发人员在编写并发应用程序时最常犯的错误之一。让我们看一个具体的例子,然后我们将定义发生此类错误的条件以及如何防止发生这类错误。 在下面的示例中,我们初始化一个切片,然后在作为新goroutine执行的闭包中访问这个元素: s := …...

Pytest教程:一文了解如何使用 pytest_runtest_makereport 修改 Pytest 测试报告内容

在软件测试过程中&#xff0c;生成清晰、易读的测试报告对于团队交流、问题追踪和项目进度评估至关重要。Pytest 是一个功能强大的 Python 测试框架&#xff0c;它不仅支持丰富的断言和测试用例组织方式&#xff0c;还提供了灵活的插件系统和钩子函数&#xff0c;可以帮助我们定…...

《高通量测序技术》分享,生物信息学生信流程的性能验证,以肿瘤NGS基因检测为例。

这是这本书&#xff0c;第四章第五节的内容&#xff0c;这一部分是以NGS检测肿瘤基因突变为例&#xff0c;描述了其原理和大概流程&#xff0c;这和以前我分享的病原宏基因组高通量测序性能确认方案可以互相补充&#xff0c;大家可以都看一下&#xff0c;但是想要真正的弄懂&am…...

Django+Celery框架自动化定时任务开发

本章介绍使用DjCelery即DjangoCelery框架开发定时任务功能&#xff0c;在Autotestplat平台上实现单一接口自动化测试脚本、业务场景接口自动化测试脚本、App自动化测试脚本、Web自动化测试脚本等任务的定时执行、调度、管理等&#xff0c;从而取代Jenkins上的定时执行脚本和发送…...

解决element-plus table组件 fixed=“right“(left)浮动后横向滚动文字穿透的问题

BUG 版本&#xff1a;element-plus 2.6.1 浏览器&#xff1a;360极速浏览器22.1 (Chromium内核) 组件&#xff1a;el-table组件 问题&#xff1a;在头部/尾部浮动加上斑马条纹后&#xff0c;横向滚动存在文字穿透的问题。具体如图&#xff1a; 白色背景行的文字&#xff0c…...

【opencv】示例-distrans.cpp 距离变换

stuff.jpg #include <opencv2/core/utility.hpp> // 包含OpenCV中的核心功能支持库 #include "opencv2/imgproc.hpp" // 包含OpenCV中的图像处理库 #include "opencv2/imgcodecs.hpp" // 包含OpenCV中的图像编解码库 #include "open…...

LVGL V8 代码细读——极致的链表使用

极致的链表的使用 序章碎碎念从redis源码里掏出来的adlist极致的精简的list.hlvgl对链表的巧思lv_ll尾记 序章碎碎念 对于链表&#xff0c;大家应该都不陌生。学过数据结构的&#xff0c;都知道它作为链式储存的基础&#xff0c;重要性不言而喻。 由于本人自动化专业&#xff…...

蓝桥杯第十二届c++大学B组详解

目录 1.空间 2.直线 3.路径 4.卡片 5.货物摆放 6.时间显示 7.砝码称重 8.杨辉三角 9.双向排序 10.括号序列 1.空间 题目解析&#xff1a;1Byte 8bit 1kb 1024B 1MB 1024kb; 先将256MB变成Byte 256 * 1024 * 1024; 再将32位 变成Byte就是 32 / 8 4&#xff1b;…...

Tubi 十岁啦!

Tubi 今年十岁了&#xff0c;这十年不可思议&#xff0c;充满奇迹&#xff01; 从硅谷一个名不见经传的创业小作坊&#xff0c;转变成为四分之一美国电视家庭提供免费流媒体服务的北美领先的平台&#xff1b; 从费尽心力终于签下第一笔内容合作协议&#xff0c;到现在与 450 …...

Qt C++ 实现文件监视源码

以下是使用Qt C++实现文件监视的一个简单示例代码: #include <QCoreApplication> #include <QFileSystemWatcher> #include <QDebug>int main(int argc, char *argv[...

蓝桥杯第十一届c++大学B组详解

目录 1.字符串排序 2.门牌制作 3.即约分数 4.蛇型填数 5.跑步锻炼 6.七段码 7.成绩统计 8.回文日期 9.字串分值和 10.平面切分 1.字符串排序 题目解析&#xff1a;这个题目真没搞懂。有会的大佬教我一下谢谢。 2.门牌制作 题目解析&#xff1a;出过超级多这类题目&am…...

大模型日报2024-04-10

大模型日报 2024-04-10 大模型资讯 微软研究者提出通过可视化思维提升大型语言模型的空间推理能力 摘要: 微软研究者近日提出了一种新方法&#xff0c;旨在通过可视化思维来增强大型语言模型&#xff08;LLMs&#xff09;的空间推理能力。尽管LLMs在语言理解和推理任务方面表现…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

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

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

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...