題目鏈接
難度：中等 ??????類型： DFS, 前綴和

給定一棵二叉樹，其中每個(gè)節(jié)點(diǎn)都含有一個(gè)整數(shù)數(shù)值(該值或正或負(fù))。設(shè)計(jì)一個(gè)算法，打印節(jié)點(diǎn)數(shù)值總和等于某個(gè)給定值的所有路徑的數(shù)量。注意，路徑不一定非得從二叉樹的根節(jié)點(diǎn)或葉節(jié)點(diǎn)開始或結(jié)束，但是其方向必須向下(只能從父節(jié)點(diǎn)指向子節(jié)點(diǎn)方向)。

示例：

解題思路

最樸素的思路以每一個(gè)結(jié)點(diǎn)為開始，遍歷所有路徑，這會(huì)有很多重復(fù)計(jì)算，當(dāng)前節(jié)點(diǎn)到根節(jié)點(diǎn)的和可以記錄下來(lái)，即前綴和

代碼實(shí)現(xiàn)

基本的dfs解法

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
         
        def dfs(node, cur_sum):
            cnt = 0
            if node is None:
                return 0
            cur_sum += node.val
            if cur_sum == sum:
                cnt += 1

            cnt += dfs(node.left, cur_sum)
            cnt += dfs(node.right, cur_sum)
            return cnt

        if root is None:
            return 0
      
        cnt = dfs(root, 0)

        cnt += self.pathSum(root.left, sum)
        cnt += self.pathSum(root.right, sum)
     
        return cnt

加入前綴和的dfs

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        prefix_sum = collections.defaultdict(int)
        prefix_sum[0] = 1
        def dfs(node, cur_sum):
            cnt = 0
            if node is None:
                return 0
            cur_sum += node.val
            cnt += prefix_sum[cur_sum - sum]
            prefix_sum[cur_sum] += 1
            cnt += dfs(node.left, cur_sum)
            cnt += dfs(node.right, cur_sum)
            # 唯一的關(guān)鍵點(diǎn)在于，退出當(dāng)前結(jié)點(diǎn)時(shí)，需要?jiǎng)h除當(dāng)前節(jié)點(diǎn)的記錄
            prefix_sum[cur_sum] -= 1
            return cnt

        if root is None:
            return 0
 
        return dfs(root, 0)