題目
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.
For 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.
思路
遞歸查找，每個節(jié)點判斷一下是否葉子節(jié)點波闹，如果是則判斷value之和是否與sum相同搂鲫；如果不是葉子節(jié)點庆械，就遞歸查找它的左右子節(jié)點恭垦。
python代碼
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if root == None:
return False
if root.left == None and root.right == None:
# leaf node
return root.val == sum
return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)
Path Sum
進階版Path Sum浑娜，不僅判斷是否存在這樣的路徑戳葵，而是要求給出所有滿足要求的路徑红且。
原題地址
思路
總體思想與上一題類似，但是需要增加一個參數(shù)list來保存路徑片部，所以需要重新寫一個遞歸函數(shù)镣衡。注意往list里append值之后要對應(yīng)的pop，否則后續(xù)對list的操作也會反映到最終結(jié)果上档悠，因為最終返回的是一個List[List[int]]廊鸥，其中的每個list是淺拷貝。
python代碼
# 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 search(self, root, sum, ls):
if root == None:
return
if root.left == None and root.right == None:
# leaf node
if sum == root.val:
ls.append(root.val)
self.result.append(ls[:])
ls.pop()
else:
# not leaf node
ls.append(root.val)
self.search(root.left, sum-root.val, ls)
self.search(root.right, sum-root.val, ls)
ls.pop()
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
self.result = []
self.search(root, sum, [])
return self.result
