題目連結: https://leetcode.com/problems/path-sum/

其他人寫的解法: https://zxi.mytechroad.com/blog/tree/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)
    }
}