代码一
用list或者字符串方式返回二叉树的所有路径:https://www.cnblogs.com/panweiwei/p/13752895.html
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if not root:
return []
res = []
road = []
self.pre_order(root, sum, res, road)
return res
def pre_order(self, node, total, res, road):
# 当前节点为空,直接return
if not node:
return
# 否则将当前节点加入路径中
road.append(node.val)
# 目标值减掉当前节点的值
total -= node.val
# 当前节点是叶子、且和为目标值,则将路径加入外层list中
if total == 0 and not node.left and not node.right:
res.append(list(road))
# 前序式递归当前节点的左右子树
self.pre_order(node.left, total, res, road)
self.pre_order(node.right, total, res, road)
# 每趟递归前将当前节点pop()
road.pop()
# 返回外层list
return res
代码二
class Solution(object):
def pathSum(self, root, sumt):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
ans = []
if not root:
return ans
stack = [(root, [root.val])]
while stack:
node, temp = stack.pop()
if not node.left and not node.right and sum(temp) == sumt:
ans.append(temp)
if node.left:
stack.append((node.left, temp + [node.left.val]))
if node.right:
stack.append((node.right, temp + [node.right.val]))
return ans[::-1]