力扣---437. 路径总和 III

allWu / 2023-05-16 / 原文

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

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

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：

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

提示:

二叉树的节点个数的范围是 [0,1000]
-109 <= Node.val <= 109
-1000 <= targetSum <= 1000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/path-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

先用 list 存储路径变量试试（时间复杂度 O(n^2)）

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        return dfs(root, new ArrayList<>(), targetSum);
    }
    private int dfs(TreeNode root, List<Integer> list, int targetSum) {
        if (root == null) {
            return 0;
        }
        // 此处最后一个测试用例，使用 int 的话，会存在溢出问题。
        long sum = 0L;
        int count = 0;
        list.add(root.val);
        for (int i = list.size() - 1; i >= 0; i --) {
            sum += list.get(i);
            if (sum == targetSum) {
                count ++;
            }
        }
        int sumLeft = dfs(root.left, list, targetSum);
        int sumRight = dfs(root.right, list, targetSum);
        list. remove(list.size() - 1);
        return sumLeft + sumRight + count;
    }
}