本文共 1001 字,大约阅读时间需要 3 分钟。
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22
,
5 / \ 4 8 / / \ 11 13 4 / \ / \7 2 5 1
Return:
[ [5,4,11,2], [5,8,4,5]]
和112. Path Sum差别不大,多保存一下路径即可。
stack中保存的是当前节点,当前path所有节点的val(这是一个list),和当前path的sum。
class Solution: def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]: if root is None: return root stack=[(root, [root.val] ,root.val)] final=[] while stack: root, lis, listsum=stack.pop(0) if root.left is None and root.right is None: if listsum==sum: final.append(lis) else: continue if root.left: stack.append((root.left, lis+[root.left.val], listsum+root.left.val)) if root.right: stack.append((root.right, lis+[root.right.val], listsum+root.right.val)) return final
转载地址:http://ldrbb.baihongyu.com/