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.