跳至主要內容

0113. 路径总和 II

ITCharge大约 2 分钟

0113. 路径总和 IIopen in new window

  • 标签:树、深度优先搜索、回溯、二叉树
  • 难度:中等

题目链接

题目大意

描述:给定一棵二叉树的根节点 root 和一个整数目标 targetSum

要求:找出「所有从根节点到叶子节点路径总和」等于给定目标和 targetSum 的路径。

说明

  • 叶子节点:指没有子节点的节点。
  • 树中节点总数在范围 [0,5000][0, 5000] 内。
  • 1000Node.val1000-1000 \le Node.val \le 1000
  • 1000targetSum1000-1000 \le targetSum \le 1000

示例

  • 示例 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
输出:[]

解题思路

思路 1:回溯

在回溯的同时,记录下当前路径。同时维护 targetSum,每遍历到一个节点,就减去该节点值。如果遇到叶子节点,并且 targetSum == 0 时,将当前路径加入答案数组中。然后递归遍历左右子树,并回退当前节点,继续遍历。

具体步骤如下:

  1. 使用列表 res 存储所有路径,使用列表 path 存储当前路径。
  2. 如果根节点为空,则直接返回。
  3. 将当前节点值添加到当前路径 path 中。
  4. targetSum 减去当前节点值。
  5. 如果遇到叶子节点,并且 targetSum == 0 时,将当前路径加入答案数组中。
  6. 递归遍历左子树。
  7. 递归遍历右子树。
  8. 回退当前节点,继续递归遍历。

思路 1:代码

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        res = []
        path = []

        def dfs(root: TreeNode, targetSum: int):
            if not root:
                return
            path.append(root.val)
            targetSum -= root.val
            if not root.left and not root.right and targetSum == 0:
                res.append(path[:])
            dfs(root.left, targetSum)
            dfs(root.right, targetSum)
            path.pop()

        dfs(root, targetSum)
        return res

思路 1:复杂度分析

  • 时间复杂度O(n2)O(n^2),其中 nn 是二叉树的节点数目。
  • 空间复杂度O(n)O(n)。递归函数需要用到栈空间,栈空间取决于递归深度,最坏情况下递归深度为 nn,所以空间复杂度为 O(n)O(n)