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.
典型的DFS, 然后需要将目前的path sum一起append进入stack里面, 然后判断path sum 是否跟给的sum相等并且是leaf, 即可.
1. Constraints
1) can be empty
2. IDeas
DFS: T:O(n) S: T(n)
3. Code
3.1) iterable
# iterable class Solution:
def pathSum(self, root, s):
if not root: return False
stack =[(root, root.val)]
while stack:
node, ps = stack.pop()
if ps == s and not node.left and not node.right:
return True
if node.left:
stack.append((node.left, ps + node.left.val))
if node.right:
stack.append((node.right, ps + node.right.val))
return False
3.2) recursive way.
class Solution:
def pathSum(self, root, s):
if not root: return False
if s- root.val == 0 and not root.left and not root.right:
return True
return self.pathSum(root.left, s- root.val) or self.pathSum(root.right, s- root.val)
4. Test cases
1) edge case
2) s= 9
5
/ \
4 8