Swift solution - Prefix Sum 100% beats


  • 0
    class Solution {
        func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
            guard let root = root else {
                return 0
            }
            
            var preSum = [Int: Int]()
            preSum[0] = 1
            
            return backtrack(root, 0, sum, &preSum)
        }
        
        func backtrack(_ root: TreeNode?, _ sum: Int, _ target: Int, _ preSum: inout [Int: Int]) -> Int {
            guard let root = root else {
                return 0
            }
            
            var sum = sum
            sum += root.val
            var result = preSum[sum - target] ?? 0
            
            preSum[sum] = (preSum[sum] ?? 0) + 1
            result += (backtrack(root.left, sum, target, &preSum) + backtrack(root.right, sum,  target, &preSum))
            preSum[sum] = (preSum[sum] ?? 0) - 1
            
            return result
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.