题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。

示例:

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

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

  • 返回: 3

  • 解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]

提示：

节点总数 <= 10000

题目思考

  1. 如何快速计算任意路径的和?
  2. 如何快速得到指定和的路径数目?

解决方案

思路

  • 要想得到任意从上到下的路径的和, 很容易想到类似数组前缀和的做法
    • 例如对于上述示例, 要想得到最右侧 4->1 的路径和, 我们可以通过计算根节点到节点 1 和节点 8 的前缀和差值来得到: sum(5->8->4->1) - sum(5->8)
  • 通过这样预处理, 我们可以得到任意从上到下路径的和, 那如何快速得到指定和的路径数目呢?
    • 我们可以额外引入一个计数字典 sumCnt, 来统计当前路径已经遍历过的所有节点的前缀和的计数, 注意初始化sumCnt[0] = 1, 代表路径没有任何节点的情况
    • 在遍历当前节点时, 假设其前缀和为 curSum, 目标路径和为 sum, 那么以当前节点为终点的所有路径中, 路径和为 sum 的路径数目即为 sumCnt[curSum - sum], 累加所有节点的这一数目, 就得到了最终结果
  • 下面代码中有详细的注释, 方便大家理解

复杂度

  • 时间复杂度 O(N): 每个节点只会被遍历一次
  • 空间复杂度 O(logN): 递归调用最多使用 O(logN) 栈空间, 而前缀和计数字典也会存当前路径上的节点, 这部分也是 O(logN)

代码

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        # 递归+前缀和计数字典
        # sumCnt是前缀和计数字典{curSum:cnt}, 统计当前路径上前缀和是curSum的路径数目cnt
        sumCnt = collections.defaultdict(int)
        # 显然刚开始时就存在前缀和是0的一种情况, 即空路径
        sumCnt[0] = 1
        # res记录最终满足条件的路径数目
        res = 0

        def dfs(node, curSum):
            nonlocal res
            if not node:
                # 当前节点为空, 返回
                return
            # 更新当前前缀和
            curSum += node.val
            # 以当前节点为终点的满足条件的路径数目为sumCnt[curSum - sum], 累加到最终结果中
            res += sumCnt[curSum - sum]
            # 当前前缀和计数+1, 在遍历子树中可以被用到
            sumCnt[curSum] += 1
            # 继续递归左右子树
            dfs(node.left, curSum)
            dfs(node.right, curSum)
            # 最后恢复现场, 因为退出当前递归函数后, 当前节点就不在路径上了, 所以其计数要-1
            sumCnt[curSum] -= 1

        dfs(root, 0)
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我