路径总和 II

标签: 深度优先搜索 回溯 二叉树

难度: Medium

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

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

 

示例 1:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]

示例 2:

输入:root = [1,2,3], targetSum = 5
输出:[]

示例 3:

输入:root = [1,2], targetSum = 0
输出:[]

 

提示:

  • 树中节点总数在范围 [0, 5000]
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

Submission

运行时间: 56 ms

内存: 16.2 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        result = []

        def dfs(root, path, k):
            if root is None:
                return

            path.append(root.val)
            if root.val == k and root.left is None and root.right is None:
                result.append(list(path))

            dfs(root.left, path, k-root.val)
            dfs(root.right, path, k-root.val)
            path.pop()
        
        dfs(root, [], targetSum)
        return result
            

Explain

该题采用深度优先搜索(DFS)的方法。从根节点开始,遍历整棵二叉树,并记录从根到当前节点的路径。当遍历到叶子节点,且路径上节点值的总和等于目标和时,将该路径加入结果列表。在递归回溯时,要从路径中删除当前节点,以便尝试其他路径。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        result = []

        def dfs(root, path, k):
            if root is None:
                return

            path.append(root.val)
            # 如果当前节点是叶子节点且节点值等于目标和,则找到一条满足条件的路径
            if root.val == k and root.left is None and root.right is None:
                result.append(list(path))
            
            # 递归遍历左子树和右子树
            dfs(root.left, path, k-root.val)
            dfs(root.right, path, k-root.val)
            # 回溯时从路径中删除当前节点
            path.pop()
        
        dfs(root, [], targetSum)
        return result

Explore

在递归函数中使用`path.append(root.val)`和`path.pop()`是为了记录和维护从根节点到当前节点的路径。这种操作称为回溯。当递归调用进入下一层时,`path.append`会添加当前节点的值到路径中。当从一个节点返回到其父节点时,`path.pop`会移除当前节点的值,这样路径就可以正确地反映从根节点到父节点的有效路径。这样的操作简化了路径管理,避免了额外的空间和复杂的路径复制操作,使代码更简洁、更高效。

这个条件确保了只有在叶子节点处才检查路径总和。在二叉树中,叶子节点定义为没有子节点的节点。此条件通过检查`root.left is None and root.right is None`来验证一个节点是否为叶子节点。如果这个条件在非叶子节点被满足,比如中间某个节点的路径总和已经等于`k`,但该节点下还有其他子节点,则可能会错过包含更完整路径的正确解,因为实际上这条路径并没有结束。

如果所有节点的值都大于0,而目标和`targetSum`是一个负数,那么算法将不会找到任何匹配的路径。因为随着树的深入,路径的总和只会增加,不可能达到一个负数的目标和。因此,`dfs`函数在这种情况下会遍历整个树,但不会在`result`中添加任何路径,最终返回一个空的列表。

深度优先搜索(DFS)和广度优先搜索(BFS)都可以用来解决路径总和问题,但它们各有优缺点。DFS通过递归实现,代码相对简洁,且由于它深入到叶节点,可以立即判断路径总和是否符合条件。其缺点是在最坏情况下可能会持有较深的调用堆栈。相比之下,BFS使用队列实现,可以逐层处理节点,有助于快速排除一些不可能的路径,特别是在路径和过大时。但BFS需要额外的空间来存储每一层的节点和路径,对于路径总和问题,可能效率不如DFS。