Python3 深度优先搜索,维护一个路径列表。如果规定了结点值的正负性,还可以剪枝。否则,这里只能递归到叶子结点了。叶子节点且满足和的条件,把path加入res结果集。满足不满足,都要把节点踢出path,以便其他路径的递归。
class Solution: def FindPath(self , root: TreeNode, target: int) -> List[List[int]]: res, path = [], [] def recur(root, tar): if not root: return path.append(root.val) # 加入路径 tar = tar - root.val if tar == 0 and not root.left and not root.right: res.append(list(path)) recur(root.left,tar) recur(root.right,tar) path.pop() # 弹出路径 recur(root,target) return res

京公网安备 11010502036488号