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
    else if (root.left == null && root.right == null) return targetSum == root.`val`
    else {
        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).

只需要用给定和target减去节点值，最终结束条件判断target==0即可