Leetcode—437路径总和II

题目描述

给定一个二叉树,它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。

示例

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

解题思路:

递归,首先从根节点进行递归,然后再从子节点进行递归,判断路径上是否出现和为目标值的路径。

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def __init__(self):
        self.result = []
    def pathSum(self, root, sum):
        if not root:
            return 0
        def Search(node, sum, tempSum, tempList):
            if node is None:
                return
            tempSum += node.val
            if tempSum == sum:
                tempList.append(node.val)
                self.result.append(tempList)
            Search(node.left, sum, tempSum, tempList + [node.val])
            Search(node.right, sum, tempSum, tempList + [node.val])
        Search(root, sum, 0, [])
        self.pathSum(root.left, sum)
        self.pathSum(root.right, sum)
        return self.result

n10 = TreeNode(10)
n5 = TreeNode(5); n_3 = TreeNode(-3)
n3 = TreeNode(3); n2 = TreeNode(2); n11 = TreeNode(11)
n9 = TreeNode(3); n_2 = TreeNode(-2); n1 = TreeNode(1)
n10.left = n5; n10.right = n_3
n5.left = n3; n5.right = n2; n_3.right = n11
n3.left = n9; n3.right = n_2; n2.right = n1
S = Solution()
print(S.pathSum(n10, 8))

 

 

热门文章

暂无图片
编程学习 ·

sqlserver:临时表的删除

遇到一个坑: 某天,定时作业失败了多次,但代码没变动,这就奇了怪了。。 结果:经检查,每次执行的时候,临时表若存在,就会失败。 分析:当初不写删除临时表,是查询了临时表的定义,会话内自动结束,不知道是哪出现了问题。 解决: if OBJECT_ID(tempdb..#tempList) is no…
暂无图片
编程学习 ·

达梦数据守护集群(dmwatch)启停方式

注: 在$DM_HOME/bin目录下执行相关脚本。 停止集群:关闭确认监视器:./DmMonitorServiceDMMONITOR stop 关闭备库守护进程:./DmWatcherServiceDM2 stop 关闭主库守护进程:./DmWatcherServiceDM1 stop 关闭备库数据库服务:./DmServiceDM2 stop 关闭主库数据库服务:./D…
暂无图片
编程学习 ·

Spring——Bean scope

Spring framework 支持6个范围(scope),其中4个只能在用web-aware时才能使用。当然,你也可以创建自定义范围。singleton : spring默认就是singleton,即在注册该bean的时候,会把这个bean存储到单列bean缓存,以后对该bean的所有的后续请求和引用都会返回缓存中的这一个bean…
暂无图片
编程学习 ·

Python入门的学习心得

由于我是自学Python,非科班出生,所以只能分享一些关于我的学习心得,如果有不对地方欢迎指正。不过非科班出生虽然是一个痛点,但是在工作上,我其实不输给我其他同事,这点我倒是很有自信,而且我也统一一句话“目前互联网上的免费编程课程,足够让你成为一个合格的码农”。…
暂无图片
编程学习 ·

solr自动更新索引,tomcat+solr

核心文件夹: tomcat-8.0.35-search------端口8888 solr-7.2.0------端口8984 核心配置: 用于配置solr索引的定时增量更新和全部更新,两个文件保持一致就可以。 /tomcat/tomcat-8.0.35-search/bin/solr/conf/dataimport.properties /solr-7.2.0/server/solr/chuai/conf/datai…
暂无图片
编程学习 ·

面试题:从 URL 在浏览器被输入到页面展现的过程中发生了什么?

曾经有这么一道面试题:从 URL 在浏览器被被输入到页面展现的过程中发生了什么?相信大多数准备过的同学都能回答出来,但是如果继续问:收到的 HTML 如果包含几十个图片标签,这些图片是以什么方式、什么顺序、建立了多少连接、使用什么协议被下载下来的呢?要搞懂这个问题,我…
暂无图片
编程学习 ·

应用10秒部署、成本降低50% 阿里云serverless容器改写云计算极限

在将应用部署时间从以天计缩短到以小时计后,云计算正进入秒计时代:阿里云推出的最新计算形态Serverless容器服务改写了云计算极限,单实例启动时间为创世界纪录的10秒,1分钟可弹出1000实例,这使按需按秒计费成为现实,在云计算大大降低计算成本的基础上,让总计算成本再次降…
暂无图片
编程学习 ·

动态任务

1.任务句柄 /* LED任务句柄 */ static TaskHandle_t LED_Task_Handle; 2.任务创建函数 BaseType_t xTaskCreate( TaskFunction_t pxTaskCode, //任务函数const char * const pcName, //任务名称const uint16_t usStackDepth, //堆栈大小void * const pvParamet…
暂无图片
编程学习 ·

Java程序员技能图谱—必须具备的6个技能!

作为历史最为悠久的编程语言,Java的发展势头一直非常好,而Java从业人员的选择范围也非常多,大致上可以将Java开发人员分为两类,一类是技术人员,一类是管理人员。无论是哪一类,想要成为一名优秀的Java开发工程师,有些技能是必须要具备的。下面,整理的优秀的Java开发人员…
暂无图片
编程学习 ·

Android 解析jwt遇到java.lang.IllegalArgumentException: bad base-64

解析jwt的时候遇到了java.lang.IllegalArgumentException: bad base-64 百思不得其解 按照网上说的:Android&ios java 这俩咋就不好使呢? 后来我看了篇帖子说 android开发中的bad base-64错误在涉及到服务器的软件中,由于使用android的Base64解码功能,而服务器端加密为…
暂无图片
编程学习 ·

JavaScript-从入门到入土(五)

BOM BOM(Browser Object Model): 浏览器对象模型,是用来描述与浏览器进行交互的方法和接口 BOM下面有一个核心的对象 – window对象。 window下面的常用的事件操作: onload() 页面内容加载完成后执行这里的代码 onscroll() 浏览器的滚动条触发时触发此事件 onresize(…
暂无图片
编程学习 ·

靶机实战(DC-4)

DC-4实验环实验过程信息收集主机发现端口扫描服务发现网站指纹漏洞发现漏洞利用提权总结 实验环 靶机:DC-4 测试机:kali(IP:192.168.186.128),win10 实验过程 信息收集 主机发现 netdiscover -I eth0 -r 192.168.186.0/24 nmap -sn 192.168.186.0/24 arp-scan -l ,arp-sc…
暂无图片
编程学习 ·

算子

算子:是一个函数空间到函数空间上的映射O:X→X。广义上的算子可以推广到任何空间,如内积空间等。 应用领域:数理科学 别 称:算符 外文名 :operator 应用领域:数理科学算子解释广义的算子, 对任何函数进行某一项操作都可以认为是一个算子,甚至包括求幂次,开方…
暂无图片
编程学习 ·

setuptools Command Reference

https://setuptools.readthedocs.io/en/latest/setuptools.html#command-reference alias - Define shortcuts for commonly used commands bdist_egg - Create a Python Egg for the project develop - Deploy the project source in “Development Mode” egg_info - Create …
暂无图片
编程学习 ·

论面向服务架构设计及其应用

在准备架构师考试过程中发现可供参考的论文范围非常少且内容陈旧给学习带来很大烦恼,通过考试后把我准备的论文共享出来水平有限但内容格式迎合考试,希望给大家一个参考。范文以“论面向服务架构设计及其应用”为题书写,希望对大家有所帮助。【摘要】2017年5月,我参加了某省…
暂无图片
编程学习 ·

ROS成长-wiki-ros教程整理 二 环境搭建

此处学习是通过catkin 编译方式来学习的。 1、创建个人的工作文件夹,此文件夹是之后学习的,存放程序的根目录 mkdir -p ~/catkin_ws/src 2、创建环境 cd ~/catkin_ws/ catkin_make catkin_make 命令是创建工作区的快捷命令,第一次在工作空间中运行它,它将在工作文件夹中的“…
暂无图片
编程学习 ·

ConcurrentHashMap 在 Java7 和 8 有何不同?

ConcurrentHashMap 在 Java7 和 8 有何不同? 文章目录ConcurrentHashMap 在 Java7 和 8 有何不同?前言1.Java 72.Java 83.重要的方法回顾3.1 Node 数组3.2 put 方法3.3 get 方法4.对比Java7 和Java8 的异同和优缺点4.1 数据结构不同4.2 并发度4.3 保证并发安全的原理4.4 遇到…
暂无图片
编程学习 ·

《MySQL数据库》常用函数整理

以下内容,是我整理出来的比较常用的字符串函数,数值函数,日期函数。第一类:字符串函数1、conv(n,from_base,to_base):对from_base进制的数n,转成to_base进制的表示方式(PS:进制范围为2-36进制,当to_base是负数时,n作为有符号数否则作无符号数)mysql> select conv(&quo…