112. 路径总和 - 简单

112. 路径总和

递归解法

• 时间复杂度
  O(n),每个节点都要访问一次
• 空间复杂度
  O(H)，其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(logN)。

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
        }
        // 递归每次用当前的 sum - 当前 root.val
        // 一直 减减减 减到 叶子节点， 就判断当前的 sum 和 root.val 是否相等即可
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
    }

广度优先解法

• 时间复杂度
  O(n),每个节点都要访问一次
• 空间复杂度
  O(N)，其中 N 是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。

func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
        guard let root = root else { // 如果 root = nil 那么就一定不存在了
            return false
        }

        var stackTree: [TreeNode] = [root]
        var treeVal: [Int] = [root.val]

        //           1
        //         /   \
        //        2     3
        //       / \    / \
        //      4   5   6  7
        // stackTree 移除 1 添加 2 3,同时 treeVal 移除 1.val 添加 1+2.val ，1+3.val
        // stackTree 移除 2 添加 4 5,同时 treeVal 移除 2.val 添加 2+4.val ，2+5.val
        // stackTree 移除 3 添加 6 7,同时 treeVal 移除 3.val 添加 3+6.val ，3+7.val
        while !stackTree.isEmpty {
            let tree: TreeNode = stackTree.popLast()!
            let sum = treeVal.popLast()
            if tree.left == nil, tree.right == nil {
                if sum == targetSum {
                    return true
                }
            }

            if tree.left != nil {
                stackTree.append(tree.left!)
                treeVal.append(sum! + tree.left!.val)
            }

            if tree.right != nil {
                stackTree.append(tree.right!)
                treeVal.append(sum! + tree.right!.val)
            }
        }

        return false
    }