Problem Link:
http://oj.leetcode.com/problems/path-sum/
One solution is to BFS the tree from the root, and for each leaf we check if the path sum equals to the given sum value.
The code is as follows.
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution:
# @param root, a tree node
# @param sum, an integer
# @return a boolean
def hasPathSum(self, root, sum):
"""
BFS from the root to leaves.
For each leaf, check the path sum with the target sum
"""
if not root:
return False
q = [(root,0)]
while q:
new_q = []
for n, s in q:
s += n.val
# If n is a leaf, check the path-sum with the given sum
if n.left == n.right == None:
if sum == s:
return True
else: # Continue BFS
if n.left:
new_q.append((n.left,s))
if n.right:
new_q.append((n.right,s))
q = new_q
return False
The other solution is to DFS the tree, and do the same check for each leaf node.
class Solution:
# @param root, a tree node
# @param sum, an integer
# @return a boolean
def hasPathSum(self, root, sum):
"""
DFS from the root to leaves.
For each leaf, check the path sum with the target sum
"""
# Special case
if not root:
return False
# Record the current path
path = [root]
# The path sum of the current path
current_sum = root.val
# Hash set for keeping visited nodes
visited = set()
# Start DFS
while path:
node = path[-1]
# Touch the leaf node
if node.left == node.right == None:
if sum == current_sum:
return True
current_sum -= node.val
path.pop()
else:
if node.left and node.left not in visited:
# Go deeper to the left
visited.add(node.left)
path.append(node.left)
current_sum += node.left.val
elif node.right and node.right not in visited:
# Go deeper to the right
visited.add(node.right)
path.append(node.right)
current_sum += node.right.val
else:
# Go back to the upper level
current_sum -= node.val
path.pop()
return False