|
回溯
def pathSum(self, root, targetSum):
"""
:type root: TreeNode
:type targetSum: int
:rtype: List[List[int]]
"""
if not root:
return []
res =[]
def backtrack(root,targetSum,sum,sol):
if not root.left and not root.right and sum == targetSum:
res.append(sol[:])
return
if root.left:
sum += root.left.val
sol.append(root.left.val)
backtrack(root.left,targetSum,sum,sol)
sum -= root.left.val
sol.pop()
if root.right:
sum += root.right.val
sol.append(root.right.val)
backtrack(root.right,targetSum,sum,sol)
sum -= root.right.val
sol.pop()
backtrack(root,targetSum,root.val,[root.val])
return res
dfs
def pathSum(self, root, targetSum):
"""
:type root: TreeNode
:type targetSum: int
:rtype: List[List[int]]
"""
ret = []
path = []
def dfs(root, targetSum):
if not root:
return
path.append(root.val)
targetSum -= root.val
if not root.left and not root.right and targetSum == 0:
ret.append(path[:])
dfs(root.left, targetSum)
dfs(root.right, targetSum)
path.pop()
return
dfs(root, targetSum)
return ret
|