LeetCode刷题之HOT100之路径总和Ⅲ

2024 7/20 一如既往的热,似乎已然习惯,昨晚睡眠还不错,特别是梦到了想见的人,有位女性朋友之前对我说,梦到了一个人就是在遗忘,是的,有些道理。那么,伴随着陶喆的《寂寞的季节》,我要开始做题了!
Anyway,我心中的陶喆top3 《Melody》、《寂寞的季节》、《二十二》。

1、题目描述

在这里插入图片描述

2、算法分析

遇到树相关的题目,就会想到那两个搜索遍历,BFS和DFS。这道题要求很明晰,给定一个目标值targetSum,求节点值和等于targetSum的路径数,要求限定也就是如题目所述。由于题目限定条件,那么我们遍历树的方式就只剩下DFS(深度优先搜索了),可以想到的是,遍历所有可能的路径、将符合要求的路径记录返回即可。
算法思想:

  • 递归遍历:通过递归地遍历二叉树的每个节点,确保所有可能的路径都被检查到。
  • 路径和的计算:对于每个节点,计算以该节点为起点的所有路径的和,并检查是否有任何路径的和等于给定的 targetSum。

3、代码

 public int pathSum(TreeNode root, int targetSum) {
        // 如果当前节点为空,说明已经到达叶子节点的下一层(即不存在),则返回0,因为没有路径可以形成
        if(root == null){
            return 0;
        }
        // 调用rootSum函数计算以当前节点为根的子树中,有多少条路径的和等于targetSum 
        int res = rootSum(root, targetSum);
        // 递归调用pathSum函数,分别计算左子树和右子树中满足条件的路径数量  
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        // 返回当前节点及其子树中满足条件的路径总数 
        return res;
    }
    
    // 计算以某个节点为起点,且路径和等于给定目标值的路径数量
    public int rootSum(TreeNode root, int targetSum){
        int res = 0;
        // 如果当前节点为空,说明已经到达叶子节点的下一层(即不存在),则返回0
        if(root == null){
            return 0;
        }
        // 获取当前节点的值
        int val = root.val;
        // 如果当前节点的值就等于targetSum,说明找到了一条路径(至少是一个节点),增加计数器
        if(val == targetSum){
            res++;
        }
        // 递归调用rootSum函数,分别计算左子树和右子树中,以当前节点值为起点,剩余目标值为targetSum-val的路径数量  
        // 注意:这里是从当前节点开始计算的,所以目标值要减去当前节点的值
        res += rootSum(root.left, targetSum - val);
        res += rootSum(root.right, targetSum - val);
        // 返回以当前节点为起点的所有满足条件的路径数量
        return res;
    }

看着官解做的,提交不了,类型int不够用,是哪个家伙搞得案例呀,换成long才能通过。

4、复杂度分析

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2),n为二叉树节点个数。对于每一个节点,求以该节点为起点的路径数目时,则需要遍历以该节点为根节点的子树的所有节点,因此求该路径所花费的最大时间为
    O(N),我们会对每个节点都求一次以该节点为起点的路径数目,因此时间复杂度为 O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度:O(n),递归需要在栈上开辟空间。

okok,就到这儿吧,拜拜啦!

相关推荐

  1. LeetCode笔记hot 100(一)

    2024-07-20 12:20:04       32 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 12:20:04       103 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 12:20:04       114 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 12:20:04       93 阅读
  4. Python语言-面向对象

    2024-07-20 12:20:04       99 阅读

热门阅读

  1. 白骑士的PyCharm教学目录

    2024-07-20 12:20:04       25 阅读
  2. Mathematical Problem

    2024-07-20 12:20:04       22 阅读
  3. 第六章 Spring框架深入学习(2023版本IDEA)

    2024-07-20 12:20:04       25 阅读
  4. IO文件流

    2024-07-20 12:20:04       27 阅读
  5. 游戏外挂的技术实现与五年脚本开发经验分享

    2024-07-20 12:20:04       26 阅读
  6. mysql高阶知识梳理

    2024-07-20 12:20:04       26 阅读
  7. 3.设计模式--创建者模式--工厂模式

    2024-07-20 12:20:04       24 阅读
  8. npm下载的依赖包版本号怎么看

    2024-07-20 12:20:04       27 阅读
  9. 【AI工具基础】—Kylin(一)

    2024-07-20 12:20:04       25 阅读