題目:
給定一個二叉樹和一個目标和,判斷該樹中是否存在根節點到葉子節點的路徑,這條路徑上所有節點值相加等于目标和。
說明: 葉子節點是指沒有子節點的節點。
示例:
給定如下二叉樹,以及目标和
sum = 22
,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
傳回
true
, 因為存在目标和為 22 的根節點到葉子節點的路徑
5->4->11->2
。
代碼:
# 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
"""
temp = sum
if root == None:
return False
if root.left == None and root.right == None:
if root.val == temp:
return True
else:
return False
else:
temp -= root.val
return self.hasPathSum(root.left,temp) or self.hasPathSum(root.right,temp)
# 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 not root.left and not root.right and root.val == sum:
return True
if root.left or root.right:
sum -= root.val
return self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum)
return False