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.