# LeetCode – 112. Path Sum

Time complexity: O(n)
Space complexity: O(n)

### 法ㄧ: (計算每一個到leaf node的path，看是否有某條path的sum等於targetSum)

``````    func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
guard let root = root else {
return false
}
if root.left == nil && root.right == nil {
return root.val == targetSum
}
return hasPathSum(root.left, targetSum - root.val ) || hasPathSum(root.right, targetSum - root.val )
}

``````

### 法二: (算出全部到leaf node的sum值，再看是否有sum值等於targetSum )

``````func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
if root == nil { return false }
var sumArr = [Int]()
pathSumHelper(root, 0, &sumArr)
return sumArr.contains(targetSum)
}

func pathSumHelper(_ root: TreeNode?, _ sum: Int, _ sumArr: inout [Int]) {
if root?.left == nil && root?.right == nil {
sumArr.append(sum + (root?.val ?? 0))
}
if root?.left != nil {
pathSumHelper(root?.left, sum + (root?.val ?? 0), &sumArr)
}
if root?.right != nil {
pathSumHelper(root?.right, sum + (root?.val ?? 0), &sumArr)
}
}``````