题解 | #二叉树中和为某一值的路径(二)#
二叉树中和为某一值的路径(二)
https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca
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