112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Solutions

1. DFS-递归

　　边遍历边减少 sum 的值，看最后一个叶子节点是不是等于剩下的 sum 大小。

# Time Complexity: O(n)
# Space Complexity: O(1)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return sum == root.val
        new_sum = sum - root.val
        return self.hasPathSum(root.left, new_sum) or self.hasPathSum(root.right, new_sum)
# Runtime: 44 ms, faster than 96.82% of Python3 online submissions for Path Sum.
# Memory Usage: 16 MB, less than 5.45% of Python3 online submissions for Path Sum.

2. DFS-迭代

　　需要注意 tmp_sum == node.val 的位置，一个叶子节点不满足这个等式不表示其他叶子节点不满足，所以不能想递归的时候那样直接 return 的这个等式的结果；

　　递归之所以行的通是因为在最后返回的那里取的是或，其他子树如果有真的时候也能返回正确。

# Time Complexity: O(n)
# Space Complexity: O(1)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        stack = [(root, sum)]
        while stack:
            node, tmp_sum = stack.pop()
            if not node:
                continue
            if not node.left and not node.right and tmp_sum == node.val:
                return True
            cur_sum = tmp_sum - node.val
            stack.append((node.left, cur_sum))
            stack.append((node.right, cur_sum))
        return False
# Runtime: 52 ms, faster than 63.63% of Python3 online submissions for Path Sum.
# Memory Usage: 15.6 MB, less than 5.45% of Python3 online submissions for Path Sum.

3. BFS-迭代

# Time Complexity: O(n)
# Space Complexity: O(1)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        queue = collections.deque()
        queue.append((root, sum))
        while queue:
            node, tmp_sum = queue.popleft()
            if not node:
                continue
            if not node.left and not node.right and tmp_sum == node.val:
                return True
            cur_sum = tmp_sum - node.val
            queue.append((node.left, cur_sum))
            queue.append((node.right, cur_sum))
        return False
# Runtime: 48 ms, faster than 86.92% of Python3 online submissions for Path Sum.
# Memory Usage: 16.1 MB, less than 5.45% of Python3 online submissions for Path Sum.

References

112. Path Sum