【Check 56】2024-04-19 - 437. 路径总和 III

思路

先序遍历，从根节点开始，判断是否等于targetSum，如果为否，则去检查左右节点是否等于targetSum-root.val

递归上述流程，最终可以得到从根节点出发，路径和为targetSum的数量

但是要找出所有路径，需要从每个节点出发，不单单是根节点，所以有两层递归，复杂度O(n^2)

节点数存在负数，所以递归中参数使用long，防止溢出

代码

class Solution { public int pathSum(TreeNode root, int targetSum) { if (root==null){ return 0; } //从当前节点出发 int count = rootSum(root,targetSum); //从当前节点的左子树出发 count += pathSum(root.left,targetSum); //从当前节点的右子树出发 count += pathSum(root.right,targetSum); return count; }

private int rootSum(TreeNode root, long targetSum) {
    int count = 0;

    if (root==null){
        return count;
    }
    if (root.val==targetSum){
        count++;
    }
    count += rootSum(root.left, targetSum - root.val);
    count += rootSum(root.right, targetSum - root.val);
    return count;
}

}



### 复杂度
- 时间复杂度：O(n^2)
- 空间复杂度：O(n)

larscheng / algo

【Check 56】2024-04-19 - 437. 路径总和 III #158

思路

代码