Path Sum III

Leetcode Problem 437: Path Sum III

Problem Summary

Given the root of a binary tree and an integer targetSum, return the number of downward paths (from parent to child) whose node values sum to targetSum. Paths do not need to start at the root or end at a leaf — they only need to travel strictly downward through parent-child connections.

Constraints:

• The tree has between 0 and 1,000 nodes.
• Node values are 32-bit signed integers.
• targetSum is an integer in the range [-1,000, 1,000].

Techniques

• Tree
• Depth-First Search
• Binary Tree

Solution

export class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null

    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

function checkPathSum(root: TreeNode | null, targetSum: number): number {
    if (!root) {
        return 0
    }

    const validPath = root.val === targetSum ? 1 : 0

    return validPath + checkPathSum(root.left, targetSum - root.val) + checkPathSum(root.right, targetSum - root.val);
}

function pathSum(root: TreeNode | null, targetSum: number): number {
    if (!root) {
        return 0
    }

    let rootCount = checkPathSum(root, targetSum)
    let countLeft = pathSum(root.left, targetSum)
    let countRight = pathSum(root.right, targetSum)

    return rootCount + countLeft + countRight
}