题目

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1

返回:

[ [5,4,11,2], [5,8,4,5] ]

解题思路

和路径总和非常相似，不过这次是需要保存所有符合要求的路径。

依旧DFS，用0表示节点没有被访问过，用1表示节点被访问过。

若当前pop出的元素标记为0时，加到总和里，并且访问状态变成1。若当前的节点标记为1，并且是叶子节点，并且cur_sum == target_sum，把路径加到返回值中

时间复杂度$o(n)$

代码

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]: if not root: return [] target_paths = [] stack = [(root, 0)] cur_sum = 0 visited_path = [] while stack: p, stat = stack.pop() if stat == 0: stack.append((p, 1)) cur_sum += p.val visited_path.append(p.val) if p.left: stack.append((p.left, 0)) if p.right: stack.append((p.right, 0)) else: if (not p.left) and (not p.right) and cur_sum == sum: target_paths.append(visited_path[::]) cur_sum -= p.val visited_path.pop() return target_paths