【Leetcode刷题Python】113. 路径总和 II

简介: LeetCode上113号问题"路径总和 II"的Python实现,通过深度优先搜索来找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

1 题目

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

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

示例 1:
在这里插入图片描述

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

示例 2:

输入:root = [1,2,3], targetSum = 5
输出:[]

示例 3:

输入:root = [1,2], targetSum = 0
输出:[]

2 解析

采用深度优先搜索的方式,枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点,且此时路径和恰为目标和时,我们就找到了一条满足条件的路径。

3 Python实现

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
    res = []
    path = []
    def dfs(node, n):
        if not node:
            return 
        path.append(node.val)
        n -=node.val
        # 即是叶子结点,也路径总合为targetSum
        if not node.left and not  node.right and n==0:
            res.append(path[:])
        dfs(node.left,n)
        dfs(node.right,n)
        path.pop()
    dfs(root,targetSum)
    return res
目录
相关文章
|
2月前
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
27 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
2月前
|
数据采集 Python
Python实用记录(七):通过retinaface对CASIA-WebFace人脸数据集进行清洗,并把错误图路径放入txt文档
使用RetinaFace模型对CASIA-WebFace人脸数据集进行清洗,并将无法检测到人脸的图片路径记录到txt文档中。
43 1
|
2月前
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
29 0
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
29 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
2月前
|
搜索推荐 Python
Leecode 101刷题笔记之第五章:和你一起你轻松刷题(Python)
这篇文章是关于LeetCode第101章的刷题笔记,涵盖了多种排序算法的Python实现和两个中等难度的编程练习题的解法。
23 3
|
2月前
|
IDE 开发工具 iOS开发
Python编程案例:查找指定文件大小的文件并输出路径
Python编程案例:查找指定文件大小的文件并输出路径
26 3
|
3月前
|
Python
python之路径 | 11
python之路径 | 11
|
2月前
|
Python
Python实用记录(十二):文件夹下所有文件重命名以及根据图片路径保存到新路径下保存
这篇文章介绍了如何使用Python脚本对TTK100_VOC数据集中的JPEGImages文件夹下的图片文件进行批量重命名,并将它们保存到指定的新路径。
35 0