原題
給出一個(gè)二叉樹(shù)和一個(gè)sum, 判斷是否存在一條自根節(jié)點(diǎn)到葉節(jié)點(diǎn)路徑钱磅，使路徑和等于sum
樣例
給出下面的二叉樹(shù) 和 sum = 22
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 True 因?yàn)?->4->11->2 的和等于22
解題思路
- 二叉樹(shù)遍歷
- 如果找到一個(gè)根到葉的路徑求和，如果等于sum直接返回True
完整代碼
# 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 hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if not root:
return False
if self.helper(root, 0, sum) == True:
return True
return False
def helper(self, root, subSum, sum):
if root.left == None and root.right == None:
if subSum + root.val == sum:
return True
if root.left and self.helper(root.left, subSum + root.val, sum):
return True
if root.right and self.helper(root.right, subSum + root.val, sum):
return True
