112. Path Sum
https://leetcode.com/problems/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.
For 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.
Solution
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
# iteratively
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if not root:
return False
if not root.left and not root.right and root.val == sum:
return True
stack = [(root, root.val)]
while stack:
node, val = stack.pop()
if not node.left and not node.right and val == sum:
return True
if node.left:
stack.append((node.left, val + node.left.val))
if node.right:
stack.append((node.right, val + node.right.val))
return False
'''
# recursively
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if not root:
return False
if not root.left and not root.right and root.val == sum:
return True
return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
'''
113. Path Sum II
https://leetcode.com/problems/path-sum-ii/
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/
4 8
/ /
11 13 4
/ /
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
Solution
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def pathSum(self, root, s):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if not root:
return []
res = []
stack = [(root, [root.val])]
while stack:
cur, ls = stack.pop()
if not cur.left and not cur.right and sum(ls) == s:
res.append(ls)
if cur.left:
stack.append((cur.left, ls+[cur.left.val]))
if cur.right:
stack.append((cur.right, ls+[cur.right.val]))
return res
'''
# recursively
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if not root:
return []
if not root.left and not root.right and sum == root.val:
return [[root.val]]
temp = self.pathSum(root.left, sum-root.val) + self.pathSum(root.right, sum-root.val)
return [[root.val] + node for node in temp]
'''
437. Path Sum III
https://leetcode.com/problems/path-sum-iii/
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/
5 -3
/
3 2 11
/
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
Solution
https://discuss.leetcode.com/topic/65100/2-python-solutions-with-detailed-explanation
Very slow. 1438ms
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
if not root:
return 0
return self.findPath(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
def findPath(self, root, sum):
res = 0
if not root:
return res
if root.val == sum:
res += 1
res += self.findPath(root.left, sum-root.val)
res += self.findPath(root.right, sum-root.val)
return res
99ms
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def helper(self, root, target, so_far, cache):
if root == None:
return 0
complement = so_far + root.val - target
result = 0
if complement in cache:
result += cache[complement]
cache.setdefault(so_far+root.val, 0)
cache[so_far+root.val] += 1
result += self.helper(root.left, target, so_far+root.val, cache)
result += self.helper(root.right, target, so_far+root.val, cache)
cache[so_far+root.val] -= 1
return result
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
return self.helper(root, sum, 0, {0:1})