路径总和 II

Leetcode Link: 113. 路径总和 II - 力扣（LeetCode） (leetcode-cn.com) 剑指 Offer 34. 二叉树中和为某一值的路径 - 力扣（LeetCode）

题目

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

本题关键

1. 找到路径而非返回 True 和 False
2. 路径只可能是根节点到叶子节点

叶子节点 是指没有子节点的节点。

解法一

思路：回溯+DFS，注意需要一直维护一个深度，并且及时的 append 以及 pop 每个节点的操作：判断是不是叶子节点（是否添加到结果），判断目标值还剩多少，路径维护。

题解：

class Solution:
    # lists.append(lst) 是浅拷贝，lst的值变化，会导致append中对应值变化（lst是列表类型）
    # 因此需要 lists.append(copy.deepcopy(lst))
    # 或者lists.append(lst.copy())
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        path = []
        def dfs(node, tar):
            if not node:
                return 
            # 一定要判断是不是叶子节点
            if node.val == tar and node.left==None and node.right==None :
                path.append(node.val)
                res.append(path.copy())
                path.pop()
                return
 
            path.append(node.val)
            dfs(node.left, tar-node.val)
            dfs(node.right, tar-node.val)
            path.pop()
            return 
 
        dfs(root, targetSum)
        return res
 

解法二：BFS

思路

1. 简历两个队列，一个是传统的用来存储节点的，另一个是用来存储 target 的，两者元素上意义对应
2. 这样，当我们遍历到一个叶子节点时，如果此时的 target 队列 pop 出来的是 0，则表示满足题意，我们将这条路径添加到 res
3. 但是在BFS中，没法像DFS一样自然的保存路径，我们的做法是定义一个字典变量(key: node, val: parent of key node)，用来在bfs的过程中保存每个节点的父节点，最后找到目标叶子节点后，利用这个字典找到这条路径。

解法

class Solution:
    def pathSum(self, root: TreeNode, target: int):
        if not root: return []
		# 定义字典，用来保存节点的父节点
        parents = collections.defaultdict(lambda: None)
        def get_parents(node):
            lst = [node.val]
            while(parents[node]):
                lst.append(parents[node].val)
                node = parents[node]
            return lst[::-1]
        # 一个节点队列，一个target队列
        # target中保存的是当前节点后的target
        q_node = collections.deque([root])
        q_target = collections.deque([target-root.val])
        res = []
        while(q_node):
            n = len(q_node)
            for _ in range(n):
                cur = q_node.popleft()
                cur_target = q_target.popleft()
				# 找到目标节点
                if not cur.left and not cur.right and cur_target == 0:
                    lst = get_parents(cur)
                    res.append(lst.copy())
                    continue
				# 每次要做三件事
				# 1. 添加父节点到字典 2.更新节点队列 3.更新target队列
                if cur.left: 
                    parents[cur.left] = cur
                    q_node.append(cur.left)
                    q_target.append(cur_target-cur.left.val)
                if cur.right: 
                    parents[cur.right] = cur
                    q_node.append(cur.right)
                    q_target.append(cur_target-cur.right.val)
        
        return res

启发和联系