112.path-sum.md

112. Path Sum

Test Cases

Normal Cases

Input: 
    1
  /   \
 3     4
targetSum = 4

Output: True

Input:
    1
  /   \
 3     4
targetSum = 6

Output: False

Edge / Corner Cases

• Empty tree

Input: []
Output: False 

DFS

fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
    if (root == null) return false
    
    if (root.left == null && root.right == null) {
        return targetSum == root.`val`
    }

    return hasPathSum(root.left, targetSum - root.`val`) || hasPathSum(root.right, targetSum - root.`val`)
}

// Or equivalently, we can add up to target sum:
fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
    return pathSum(root, 0, targetSum)
}

private fun pathSum(root: TreeNode?, sum: Int, target: Int): Boolean {
    if (root == null) return false
    // Process current node
    val currentSum = sum + root.`val`

    if (root.left == null && root.right == null) {
        return curretnSum == target
    }

    return pathSum(root.left, currentSum, target) ||
            pathSum(root.right, currentSum, target)
}

• Time Complexity: O(n).
• Space Complexity: O(n).

BFS

We can also use BFS to solve this problem:

• We enqueue the node and the remaining sum to the queue.
• If one of the leaf nodes has the remaining sum equal to the node value, we return true.

fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
    if (root == null) return false
    val queue = ArrayDeque<Pair<TreeNode, Int>>()
    queue.addLast(root to targetSum)
    while (queue.isNotEmpty()) {
        val (node, sum) = queue.removeFirst()
        if (node.left == null && node.right == null && node.`val` == sum) {
            return true
        }

        if (node.left != null) {
            queue.addLast(node.left to sum - node.`val`)
        }
        if (node.right != null) {
            queue.addLast(node.right to sum - node.`val`)
        }
    }
    return false
}