When I interviewed quara, they tested this question to me.
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
My code:
# 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 root==None:
return 0
count_path=self.check_path(root,sum,0)
count_path+=self.check_path(root,sum,1)
return count_path
def check_path(self,root,num,mode):
#Mode 0 choose this path
#Mode 1 do not choose the path
if root==None:
return 0
#print('mode %d root %d num %d'%(mode,root.val,num))
count=0
if root.val==num and mode==0:
count=1
left=root.left
right=root.right
count+=self.check_path(left,num-root.val,0)
count+=self.check_path(right,num-root.val,0)
return count
left=root.left
right=root.right
if mode==0:
count+=self.check_path(left,num-root.val,0)
count+=self.check_path(right,num-root.val,0)
else:
count+=self.check_path(left,num,1)
count+=self.check_path(right,num,1)
count+=self.check_path(left,num,0)
count+=self.check_path(right,num,0)
#print('num %d root %d return count %d'%(num,root.val,count))
return count