LeetCode

Appearance

437. Path Sum III ​

题目 ​

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

 

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

 

Constraints:

  • The number of nodes in the tree is in the range [0, 1000].
  • -109 <= Node.val <= 109
  • -1000 <= targetSum <= 1000
Related Topics
  • 树
  • 深度优先搜索
  • 二叉树

  • 👍 2089
  • 👎 0

    • 思路一 ​

    本题需要遍历所有父子关系路径和，在普通递归的模式上，需要使用回溯

    • 使用递归遍历整颗树，同时使用 path 记录访问的每个节点
    • 单层节点处理时
      • 依次计算根 -> 第一层 -> ... -> 节点前一层的 路径和
      • 判断 每层路径和 和 当前的路径 是否命中 targetSum, 命中则 res += 1
    • 单层递归结束后，需要结果进行回溯

    解法 ​

    python
    class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        self.res = 0

        if not root:
            return self.res


        def dfs(root: Optional[TreeNode], count, path):
            if not root:
                return

            path.append(root.val)
            count += root.val

            if count == targetSum:
                self.res += 1

            temp = count
            for i in range(len(path) - 1):
                temp -= path[i]
                if temp == targetSum:
                    self.res += 1

            dfs(root.left, count, path)

            dfs(root.right, count, path)

            path.pop()
            count -= root.val


        dfs(root, 0, [])

        return self.res

    复杂度分析 ​

    N 为二叉树的节点， H 为树的高度

    • 时间复杂度 O(N * N)
    • 空间复杂度 O(H)

    解法二 前缀和 + 递归 ​

    因为本题只需要找到满足条件的数量，而非具体的路径，可以只关注路径和 即舍去路径顺序，记录路径和 采用 dict 记录已访问过路径和，使得查找效率为 O(1)

    举个例子 targetSum = 10

    当前节点路径和为 8

    则先序路径和存在为 2 的节点的数量，即为有效路径的数量

    py
    from collections import defaultdict
# leetcode submit region begin(Prohibit modification and deletion)
# 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: Optional[TreeNode], targetSum: int) -> int:
        prefix = defaultdict(int)
        prefix[0] = 1

        def dfs(root: Optional[TreeNode], count):

            if not root:
                return 0

            count += root.val

            res = prefix[count - targetSum]

            prefix[count] += 1

            res += dfs(root.left, count)
            res += dfs(root.right, count)

            prefix[count] -= 1

            return res

        return dfs(root, 0)





        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    N 为二叉树的节点， H 为树的高度

    • 时间复杂度 O(N)
    • 空间复杂度 O(N + H)
      • N for dict
      • H for function stack