题目大意: Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
解题思路:把当前要找的sum减去node节点的值作为新的sum的值,然后递归求解左指数,递归求解右指数,直到leaf节点,判断当前剩下的sum跟leaf节点的.val是不是相同。
def pathSum(self, root, sum):
if not root:
return []
self.res = []
def dfs(node, sum, temp):
if not node:
return []
if not node.left and not node.right:
if node.val - sum == 0:
temp.append(node.val)
self.res.append(temp[:])
temp.pop()
temp.append(node.val)
sum -= node.val
dfs(node.left, sum, temp)
dfs(node.right, sum, temp)
temp.pop()
dfs(root, sum, [])
return self.res