20_路径总和

简介: 20_路径总和

路径总和

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

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

示例 1:

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

示例 2:

输入:root = [1,2,3], targetSum = 5
输出:false
解释:树中存在两条根节点到叶子节点的路径:
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3:

输入:root = [], targetSum = 0
输出:false
解释:由于树是空的,所以不存在根节点到叶子节点的路径。

【思路】

回溯+递归

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

参数:需要二叉树的根节点,还需要一个计数器,这个计数器用来计算二叉树的一条边之和是否正好是目标和,计数器为int型。

小tips:递归函数什么时候需要返回值?什么时候不需要返回值?这里总结如下三点:

  • 如果需要搜索整颗二叉树且不用处理递归返回值,递归函数就不要返回值(对应于leetcode113.路径总和ii)
  • 如果需要搜索整颗二叉树且需要处理递归返回值,递归函数就需要返回值。(对应于236.二叉树的最近公共祖先中提到)
  • 如果要搜索其中一条符合条件的路径,那么递归一定需要返回值,因为遇到符合条件的路径了就需要及时返回。(本题的情况)
bool traversal(TreeNode root, int count);//注意函数的返回值类型

2、确定终止条件

首先计数器如何统计这一条路径的和呢?

不要去累加然后判断是否等于目标和,那么代码比较麻烦,可以用递减,让计数器count初始为目标和,然后每次减去遍历路径节点上的数值。

如果最后count == 0,同时到了叶子节点的话,说明找到了目标和。

如果遍历到了叶子节点,count不为0,就是没找到。

递归终止条件代码如下:

if (cur.left == null && cur.right == null && count == 0) return true;//遇到叶子节点,并且计数为0
if (cur.left == null && cur.right == null)  return false;//遇到叶子节点而没有找到合适的边,直接返回false

3、确定单层递归的逻辑

因为终止条件是判断叶子节点,所以递归的过程中就不要让空节点进入递归了。

递归函数是有返回值的,如果递归函数返回true,说明找到了合适的路径,应该立即返回。

if (cur.left != null) {  //左(空节点不遍历)
  //遇到叶子节点返回true,则直接返回true
  if (traversal(cur.left, count - cur.left.val))  return true;//注意这里有回溯的逻辑
}
if (cur.right != null) {
  if (traversal(cur.right, count - cur.right.val))  return true;
}
return false;

以上代码中是包含着回溯的,没有回溯,如何后撤重新找另一条路径呢。

回溯隐藏在traversal(cur->left, count - cur->left->val)这里, 因为把count - cur->left->val 直接作为参数传进去,函数结束,count的数值没有改变。

为了把回溯的过程体现出来,可以改为如下代码:

if (cur.left) { // 左
    count -= cur.left.val; // 递归,处理节点;
    if (traversal(cur.left, count)) return true;
    count += cur.left.val; // 回溯,撤销处理结果
}
if (cur.right) { // 右
    count -= cur.right.val;
    if (traversal(cur.right, count)) return true;
    count += cur.right.val;
}
return false;

整体代码如下:

class Solution {
    //递归+回溯
    public boolean haspathsum(treenode root, int targetsum) {
        if (root == null) {
            return false;
        }
        targetsum -= root.val;
        // 叶子结点
        if (root.left == null && root.right == null) {
            return targetsum == 0;
        }
        if (root.left != null) {
            boolean left = haspathsum(root.left, targetsum);
            if (left) {      // 已经找到
                return true;
            }
        }
        if (root.right != null) {
            boolean right = haspathsum(root.right, targetsum);
            if (right) {     // 已经找到
                return true;
            }
        }
        return false;
    }
}
相关文章
|
Python Windows
PyCharm证书过期:Your license has expired
pycharm激活码,由于那台服务器不维护了,不好使了,你可以关注宏哥的公众号发送:激活码,Ctrl+A,Ctrl+C,然后Ctrl+V,就可以了。
5172 0
PyCharm证书过期:Your license has expired
|
SQL 机器学习/深度学习 分布式计算
Python之pyspark:pyspark的简介、安装、使用方法之详细攻略
Python之pyspark:pyspark的简介、安装、使用方法之详细攻略
Python之pyspark:pyspark的简介、安装、使用方法之详细攻略
|
消息中间件 设计模式 移动开发
高德打车通用可编排订单状态机引擎设计
订单状态流转是交易系统的最为核心的工作,订单系统往往都会存在状态多、链路长、逻辑复杂的特点,还存在多场景、多类型、多业务维度等业务特性。在保证订单状态流转稳定性的前提下、可扩展性和可维护性是我们需要重点关注和解决的问题。
高德打车通用可编排订单状态机引擎设计
Ninja is required to load C++ extensions | 问题解决
Ninja is required to load C++ extensions | 问题解决
|
10月前
|
机器学习/深度学习 传感器 运维
使用机器学习技术进行时间序列缺失数据填充:基础方法与入门案例
本文探讨了时间序列分析中数据缺失的问题,并通过实际案例展示了如何利用机器学习技术进行缺失值补充。文章构建了一个模拟的能源生产数据集,采用线性回归和决策树回归两种方法进行缺失值补充,并从统计特征、自相关性、趋势和季节性等多个维度进行了详细评估。结果显示,决策树方法在处理复杂非线性模式和保持数据局部特征方面表现更佳,而线性回归方法则适用于简单的线性趋势数据。文章最后总结了两种方法的优劣,并给出了实际应用建议。
495 7
使用机器学习技术进行时间序列缺失数据填充:基础方法与入门案例
|
12月前
|
分布式计算 大数据 Serverless
云栖实录 | 开源大数据全面升级:Native 核心引擎、Serverless 化、湖仓架构引领云上大数据发展
在2024云栖大会开源大数据专场上,阿里云宣布推出实时计算Flink产品的新一代向量化流计算引擎Flash,该引擎100%兼容Apache Flink标准,性能提升5-10倍,助力企业降本增效。此外,EMR Serverless Spark产品启动商业化,提供全托管Serverless服务,性能提升300%,并支持弹性伸缩与按量付费。七猫免费小说也分享了其在云上数据仓库治理的成功实践。其次 Flink Forward Asia 2024 将于11月在上海举行,欢迎报名参加。
608 6
云栖实录 | 开源大数据全面升级:Native 核心引擎、Serverless 化、湖仓架构引领云上大数据发展
|
弹性计算 运维 Shell
使用 shell 脚本打印图形
【4月更文挑战第29天】
234 1
|
运维 Kubernetes 监控
chaosblade
chaosblade “【5月更文挑战第5天】”
331 10
|
关系型数据库 PostgreSQL 移动开发
PostgreSQL 9.6 聚合运算180倍性能提升如何做到? 聚合代码优化OP复用浅析
PostgreSQL 9.6 内核优化之 聚合代码优化OP复用浅析 作者 digoal 日期 2016-10-08 标签 PostgreSQL , 9.6 , 内核优化 , 聚合代码优化 , OP复用 背景 聚合操作指将分组的数据聚合为一个结果输出。 聚合通常用在统
5572 0
|
并行计算 PyTorch Linux
pytorch安装GPU版本 (Cuda12.1)教程: Windows、Mac和Linux系统下GPU版PyTorch(CUDA 12.1)快速安装
pytorch安装GPU版本 (Cuda12.1)教程: Windows、Mac和Linux系统下GPU版PyTorch(CUDA 12.1)快速安装
10985 0