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

okok，就到这儿吧，拜拜啦！