力扣刷题-二叉树-路径总和

112 路径总和

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树,以及目标和 sum = 22,
image.png
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

思路

参考:https://www.programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html#%E6%80%9D%E8%B7%AF
递归函数什么时候要有返回值,什么时候没有返回值,特别是有的时候递归函数返回类型为bool类型。
那么接下来我通过详细讲解如下两道题,来回答这个问题:
112.路径总和
113.路径总和ii
这道题我们要遍历从根节点到叶子节点的路径看看总和是不是目标和。

递归

可以使用深度优先遍历的方式(本题前中后序都可以,无所谓,因为中节点也没有处理逻辑)来遍历二叉树

  1. 确定递归函数的参数和返回类型

参数:需要二叉树的节点,还需要一个计数器,这个计数器用来计算二叉树的一条边之和是否正好是目标和,计数器为int型。
再来看返回值,递归函数什么时候需要返回值?什么时候不需要返回值?这里总结如下三点:

  • 如果需要搜索整棵二叉树且不用处理递归返回值,递归函数就不要返回值。(这种情况就是本文下半部分介绍的113.路径总和ii)
  • 如果需要搜索整棵二叉树且需要处理递归返回值,递归函数就需要返回值。 (这种情况我们在236. 二叉树的最近公共祖先 中介绍)
  • 如果要搜索其中一条符合条件的路径,那么递归一定需要返回值,因为遇到符合条件的路径了就要及时返回。(本题的情况)

而本题我们要找一条符合条件的路径,所以递归函数需要返回值,及时返回,那么返回类型是什么呢?
如图所示:
image.png
图中可以看出,遍历的路线,并不要遍历整棵树(只需要有符合题意得时候 立刻返回就行),所以递归函数需要返回值,可以用bool类型表示。
所以代码如下:

# 我的问题就是遍历到一条路径底部时候 如何转到另一条路径 —— > 回溯def travelsal(self, node, count): # 递归第一步 参数为当前节点 另外采用一个计数器 遍历路径时候减去当前遍历节点的值

在python中 函数头不明确指明返回值类型 但自己要知道 返回值什么 为什么需要返回值

  1. 确定终止条件

首先计数器如何统计这一条路径的和呢?
不要去累加然后判断是否等于目标和,那么代码比较麻烦,可以用递减,让计数器count初始为目标和,然后每次减去遍历路径节点上的数值。(逆向思维)
如果最后count == 0,同时到了叶子节点的话,说明找到了目标和。
如果遍历到了叶子节点,count不为0,就是没找到。
递归终止条件代码如下:

if not node.left and not node.right and count == 0:return True # 到达叶子节点 且count为0 说明当前路径刚好符合目标
if not node.left and not node.right:return False # 到达叶子节点 但是count不为0 因为路径有很多条 到达路径时候必然是叶子节点
  1. 确定单层递归的逻辑

因为终止条件是判断叶子节点,所以递归的过程中就不要让空节点进入递归了。
递归函数是有返回值的,如果递归函数返回true,说明找到了合适的路径,应该立刻返回。
代码如下:

if node.left:count -= node.left.valif self.travelsal(node.left, count): # 递归处理节点return Truecount += node.left.val # 回溯 
# 右
if node.right:count -= node.right.valif self.travelsal(node.right, count):return Truecount += node.right.val # 回溯

完整代码:

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution(object):def hasPathSum(self, root, targetSum):""":type root: TreeNode:type targetSum: int:rtype: bool"""if not root:return False# self.travelsal(root, targetSum)return self.travelsal(root, targetSum - root.val) # 减去根节点的 再遍历之后的# 我的问题就是遍历到一条路径底部时候 如何转到另一条路径 —— > 回溯def travelsal(self, node, count): # 递归第一步 参数为当前节点 另外采用一个计数器 遍历路径时候减去当前遍历节点的值if not node.left and not node.right and count == 0:return True # 到达叶子节点 且count为0 说明当前路径刚好符合目标if not node.left and not node.right:return False # 到达叶子节点 但是count不为0 因为路径有很多条 到达路径时候必然是叶子节点# 左# if node.left:#     count -= node.left.val#     self.travelsal(node.left, count)#     count += node.left.val # 回溯 # 上面错误if node.left:count -= node.left.valif self.travelsal(node.left, count): # 递归处理节点return Truecount += node.left.val # 回溯 # 右if node.right:count -= node.right.valif self.travelsal(node.right, count):return Truecount += node.right.val # 回溯return False # 注意最后还要返回False 因为没有符合以上True的情况

迭代法

如果使用栈模拟递归的话,那么如果做回溯呢?
此时栈里一个元素不仅要记录该节点指针,还要记录从头结点到该节点的路径数值总和。

# 法二 迭代法
class Solution(object):def hasPathSum(self, root, targetSum):if not root:return False # 树为空 直接返回False# 采用前序遍历 中左右 stack = [(root, root.val)] # 栈里面存储的是节点及节点值while stack:node, path_sum = stack.pop()# 如果该节点是叶子节点了,同时该节点的路径数值等于sum,那么就返回trueif not node.left and not node.right and path_sum == targetSum:return True#  # 左节点,压进去一个节点的时候,将该节点的路径数值也记录下来if node.left:stack.append((node.left, path_sum + node.left.val))# 右节点if node.right:stack.append((node.right, path_sum + node.right.val))return False

113 路径总和2

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。(本题与上一题得区别是要找到所有的路径)
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树,以及目标和 sum = 22,
image.png

思路

113.路径总和ii要遍历整个树,找到所有路径,所以递归函数不要返回值!
如图:
image.png
代码:

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right# 本题与112题不同的是 本题要找出所有路径 所以除了count计数之外 还需要一个列表来存储路径结果
class Solution(object):def __init__(self):self.result = [] # 总的结果self.path = [] # 单条路径结果def pathSum(self, root, targetSum):""":type root: TreeNode:type targetSum: int:rtype: List[List[int]]"""# 先清空 result 和 path# self.result.clear()# self.path.clear()del self.result[:] # 注意若是 del self.result则是删除整个对象 而加了[:]是删除其中的元素del self.path[:]if not root:return self.resultself.path.append(root.val) # 把根节点放入pathself.travelsal(root, targetSum - root.val)return self.resultdef travelsal(self, node, count): # 用node表示更一般化 容易理解if not node.left and not node.right and count == 0:self.result.append(self.path[:]) # 收获结果 符合题目的单条路径加到总结果中 注意是 self.path[:]return if not node.left and not node.right:returnif node.left: # 左节点不为空 空节点不遍历self.path.append(node.left.val)count -= node.left.valself.travelsal(node.left, count) # 递归节点count += node.left.val # 回溯self.path.pop() # 回溯 pop不需要传入参数if node.right: # 右节点不为空 空节点不遍历self.path.append(node.right.val)count -= node.right.valself.travelsal(node.right, count) # 递归节点count += node.right.val # 回溯self.path.pop() # 回溯return # 不需要返回值 直接一个return就行

self.result.append(self.path) 与 self.result.append(self.path[:]) 的区别:

  1. result.append(self.path) 将 self.path 添加到 result 列表中,但实际上它是对 self.path 的引用。这意味着如果后续更改了 self.path 的值,result 列表中的相应元素也会受到影响,因为它们引用相同的对象。这是因为 self.path 是一个可变对象(例如,列表、字典),并且在列表中仅存储了对该对象的引用。
self.path = [1, 2, 3]
result = []
result.append(self.path)self.path.append(4)
print(result)  # 输出 [1, 2, 3, 4]
  1. result.append(self.path[:]) 创造了 self.path 的一个副本,并将该副本添加到 result 列表中。这意味着即使后续更改了 self.path 的值,result 列表中的元素仍然保持不变,因为它们引用的是一个独立的副本。
self.path = [1, 2, 3]
result = []
result.append(self.path[:])self.path.append(4)
print(result)  # 输出 [1, 2, 3]

总结

本篇通过leetcode上112. 路径总和 和 113. 路径总和ii 详细的讲解了 递归函数什么时候需要返回值,什么不需要返回值。
这两道题目是掌握这一知识点非常好的题目,大家看完本篇文章再去做题,就会感受到搜索整棵树和搜索某一路径的差别。
对于112. 路径总和,我依然给出了递归法和迭代法,这种题目其实用迭代法会复杂一些,能掌握递归方式就够了

参考:https://www.programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/219311.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

VRRP(虚拟路由冗余协议)

一.VRRP简介 1.VRRP是什么 Virtual route Redundancy Protocol,也叫虚拟路由器冗余协议。 利用VRRP,一组路由器协同工作,单只有一个处于Master状态,处于该状态的路由器(的接口)承担实际的数据流量转发任…

亚马逊云科技发布企业生成式AI助手Amazon Q,助力企业迈向智能化时代

(声明:本篇文章授权活动官方亚马逊云科技文章转发、改写权,包括不限于在 亚马逊云科技开发者社区、知乎、自媒体平台、第三方开发者媒体等亚马逊云科技官方渠道) 一、前言 随着人工智能技术的快速发展和广泛应用,我们…

git 上传大文件操作 lfs 的使用

我们要先去下载 下载后安装 我最后还是下载到了D:\git\Git\bin这个目录下 如何检查是否下载成功呢,用 git lfs install 在命令行运行就可以查看 下面怎么上传文件呢 首先我们还是要初始化文件的 git init 下一步输入命令 git lfs install 下一步 git lfs tra…

MySQL之DML语句

文章目录 DML语句创建表添加表字段**插入数据**查询数据更新数据替换数据删除数据清除表数据删除表 DML语句 数据操作语言DML(Data Manipulation Langua) 是SQL语言的一个分类,用于对表的数据进行增,删,改&#xff0c…

成都工业学院2021级操作系统专周课程设计FCFS,SSTF,SCAN,LOOK算法的实现

运行环境 操作系统&#xff1a;Windows 11 家庭版 运行软件&#xff1a;CLion 2023.2.2 源代码文件 #include <iostream> #include <vector> #include <algorithm> #include <random> using namespace std;// 生成随机数 int generateRandomNumber…

创建型模式之工厂模式

​ 本质&#xff1a; 实例化对象不直接使用new&#xff0c;而是用工厂代替 工厂模式分为&#xff1a; 简单工厂模式&#xff1a;用来生产同一等级结构中的任意产品&#xff08;增加新产品需要修改已有代码&#xff09;工厂方法模式&#xff1a;用来生产同一等级结构中的固定产…

vite原理

一、依赖预构建 1、为什么需要依赖预构建 CommonJS和UMD兼容性 在开发阶段中&#xff0c;vite的开发服务器将所有的代码视为原生ES模块。因此&#xff0c;vite必须先将作为CommonJS或者UMD发布的依赖项转换为ESM。 这是vite的一个特色&#xff0c;也是为什么会相对于webpack比…

21--集合小案例

案例--图书管理系统 1.创建实体类Book package com.work.pojo; /** *Author: 憨憨浩浩 *CreateTime: 2023-12-16 17:27 *Description: Book实体类 */ public class Book {private int id; // 编号private String name; // 图书名称private String author;…

MySQL,分组order by

一、创建分组 ## 创建分组 -- 返回每个发布会的参会人数 SELECT event_id,COUNT(*) as canjia_num FROM sign_guest GROUP BY event_id; 1、group by子句可以包含任意个列&#xff0c;但是但指定的所有列都是一起计算的。 group by 后2个字段一起计算的 2、group by后面可以跟…

什么是Vue?

什么是Vue 什么是Vue&#xff1f;Vue 快速入门常用指令生命周期生命周期介绍生命周期 函数调用情况 什么是Vue&#xff1f; Vue 快速入门 常用指令 生命周期 生命周期介绍 生命周期 函数调用情况

Go EASY游戏框架 之 RPC Guide 03

1 Overview easy解决服务端通信问题&#xff0c;同样使用了RPC技术。easy使用的ETCDGRPC&#xff0c;直接将它们打包组合在了一起。随着服务发现的成熟&#xff0c;稳定&#xff0c;简单&#xff0c;若是不用&#xff0c;甚至你也并不需要RPC来分解你的架构。 GRPC 有默认res…

【漏洞复现】CVE-2023-47261 Dokmee ECM信息泄露致远程命令执行

漏洞描述 Dokmee ECM是一款国外企业内容管理 (ECM) 软件。每个公司的办公室每个角落都存放着文档、记录和档案。Dokmee 一系列解决方案可以帮助您高效地组织、保护和管理这些文件。支持的文件:PDF、TIFF、Word、Excel、Auto-CAD 绘图、电子邮件等。Dokmee 可以帮助您立即实现…

10.CSS浮动

CSS浮动 1.介绍 在最初&#xff0c;浮动是用来实现文字环绕图片效果的&#xff0c;现在浮动是主流的页面布局方式之一 2.作用 让元素脱离标准流&#xff0c;同一级的浮动的元素可以并排在一排显示 3.元素浮动后的特点 脱离文档流不管浮动前是什么元素&#xff0c;浮动后&…

离散数学知识点-期末复习

目录 一、利用真值表求主析取范式、主合取范式 1.例题 二、推理证明 1.推理规则 2.例题 三、符号化命题 四、有穷集的计数 1.包含互斥原理 2.例题 ​1.文氏图法 2.包含互斥原理法 五、关系的闭包 1.三种闭包 2.Warshall算法 3.例题 六、等价关系 1.定义 2.…

Python Django Suit:构建现代化的Django后台管理

概要 Django Suit是一款为Django后台管理提供现代、优雅界面的第三方应用&#xff0c;它致力于提升Django开发者的管理体验。本文将深入介绍Django Suit的安装、配置和高级功能&#xff0c;提供详实的示例代码&#xff0c;帮助大家更好地使用和定制Django后台管理界面。 安装与…

LCR 181. 字符串中的单词反转

解题思路&#xff1a; class Solution {public String reverseMessage(String message) {message message.trim(); // 删除首尾空格int j message.length() - 1, i j;StringBuilder res new StringBuilder();while (i > 0) {while (i >…

redis-学习笔记(Jedis 通用命令)

flushAll 清空全部的数据库数据 jedis.flushAll();set & get set 命令 get 命令 运行结果展示 exists 判断该 key 值是否存在 当 redis 中存在该键值对时, 返回 true 如果键值对不存在, 返回 false keys 获取所有的 key 值 参数是模式匹配 *代表匹配任意个字符 _代表匹配一…

【Pytorch】学习记录分享3——PyTorch 自动微分与线性回归

【【Pytorch】学习记录分享3——PyTorch 自动微分与线性回归 1. autograd 包&#xff0c;自动微分2. 线性模型回归演示3. GPU进行模型训练 小结&#xff1a;只需要将前向传播设置好&#xff0c;调用反向传播接口&#xff0c;即可实现反向传播的链式求导 1. autograd 包&#x…

物流实时数仓:数仓搭建(DWD)一

系列文章目录 物流实时数仓&#xff1a;采集通道搭建 物流实时数仓&#xff1a;数仓搭建 物流实时数仓&#xff1a;数仓搭建&#xff08;DIM&#xff09; 物流实时数仓&#xff1a;数仓搭建&#xff08;DWD&#xff09;一 文章目录 系列文章目录前言一、文件编写1.目录创建2.b…

分类预测 | Matlab实现DBO-SVM蜣螂算法优化支持向量机的数据分类预测【23年新算法】

分类预测 | Matlab实现DBO-SVM蜣螂算法优化支持向量机的数据分类预测【23年新算法】 目录 分类预测 | Matlab实现DBO-SVM蜣螂算法优化支持向量机的数据分类预测【23年新算法】分类效果基本描述程序设计参考资料 分类效果 基本描述 1.Matlab实现DBO-SVM蜣螂算法优化支持向量机的…