437.path-sum-iii.md

437. Path Sum III

Double Recursion

We can find the path sum from current root, and then find the path sum from left and right child. The path sum from left and right child is the same problem, so we can use recursion to solve it.

fun pathSum(root: TreeNode?, targetSum: Int): Int {
    if (root == null) return 0
    
    // We count `sum == target` that starts from the current root.
    var count = rootSum(root, targetSum.toLong())

    // We count `sum == target` that starts from the left and right child.
    count += pathSum(root.left, targetSum)
    count += pathSum(root.right, targetSum)

    return count
}

/**
 * Find the number of paths that sum to target from the current root. (Not necessary from root to leaf)
 */
private fun rootSum(root: TreeNode?, target: Long): Int {
    if (root == null) return 0

    var count = 0
    if (root.`val`.toLong() == target) count++

    count += rootSum(root.left, target - root.`val`)
    count += rootSum(root.right, target - root.`val`)
    return count
}

// pathSum()
1           rootSum(root=1, target=5) +
 \          pathSum(root=-1, target=5)
  -1            rootSum(root=-1, target=4) + 
    \           pathSum(root=5, target=5)
     5              rootSum(root=5, target=5) +
      \             pathSum(root=0, target=5)
       0                rootSum(root=0, target=5)
                        pathSum(root=null, target=5)

// rootSum()
1           rootSum(root=1, target=5) = 1
 \          count = 0 + 1
  -1            rootSum(root=-1, target=4) = 1
    \           count = 0 + 1
     5              rootSum(root=5, target=5) = 1
      \             count = 1 + 0
       0                rootSum(root=0, target=5) = 0

• Time Complexity: O(n^2)
• Space Complexity: O(n)

WA

targetSum = 3
1 
 \
  2
   \
    3

The intuitive logic is actually 100% correct, at any given node, we want to extend the existing path sum and start a new path sum from that node. But the following implementation creates overcounting.

For the simple example A -> B -> C.

                   dfs(A, 0)
          /                      \  
     dfs(B, A)                   dfs(B, 0)
    /        \                  /         \
dfs(C, A+B)  dfs(C, 0)      dfs(C, B)     dfs(C, 0)
             ^^^^^^^^^                    ^^^^^^^^^
             // Duplicate counting.

private var count = 0

fun pathSum(root: TreeNode?, targetSum: Int): Int {
    dfs(root, targetSum, 0)
    return count
}

private fun dfs(root: TreeNode?, targetSum: Int, currentSum: Int) {
    if (root == null) return
    val newSum = root.`val` + currentSum
    if (newSum == targetSum) {
        count++
    }
    dfs(root.left, targetSum, newSum)
    dfs(root.right, targetSum, newSum)

    dfs(root.left, targetSum, 0)
    dfs(root.right, targetSum, 0)
}

Prefix Sum

TODO: Add implementation