題目連結: 437. Path Sum III

題目描述:給定一個二元樹的根節點 root 和一個整數 targetSum，求出該樹中節點值之和等於 targetSum 的 路徑 的數量。路徑不一定需要從根節點開始，也不一定需要到葉子節點結束，但必須是向下的。

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3

Python

解題思路:
這道題的最優解，是將我們在陣列問題中學到的「前綴和」思想，應用在樹的遞迴遍歷上。
當我們從根節點 root 深度優先搜尋到某個節點 node 時，我們可以計算出從 root 到 node 的路徑和，我們稱之為前綴和 curr。
如果在這條路徑上，存在一個祖先節點，其前綴和為 ancestor_sum，並且 curr - ancestor_sum == targetSum，那麼從那個祖先節點的下一個節點到 node 的這段路徑，就是一條符合條件的路徑。

以下提供兩種寫法。

寫法一(雙重遞迴)

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        ans = 0
        def dfs(node,temp):
            nonlocal ans
            if not node:
                return
            temp += node.val
            if temp == targetSum:
                ans += 1
            dfs(node.left,temp)
            dfs(node.right,temp)
        def curr(node):
            if not node:
                return
            dfs(node,0)
            curr(node.left)
            curr(node.right)
        curr(root)
        return ans

寫法二(前綴和+哈希表+DFS)

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        pre = {0:1}
        def dfs(node,curr):
            if not node:
                return 0

            curr += node.val
            count = pre.get(curr - targetSum,0)
            pre[curr] = pre.get(curr, 0)+1
            count += dfs(node.left,curr)
            count += dfs(node.right,curr)
            pre[curr] -=1
            return count
        return dfs(root,0)

演算法分析:

• 第一個方法的時間複雜度最差會造成O(n^2)，一旦樹變大時，很有可能超時。
• 第二個方法中，pre = {0: 1}代表 「數值為 0 的前綴和出現了 1 次」 ，這相當於在樹開始之前有一個「虛擬」的點，使得那些從根節點自己開始的路徑能夠被正確計算。
• curr += node.val計算從根到當前 node 的前綴和。
• count = pre.get(curr - targetSum, 0)這是核心，它在哈希表中查找 curr - targetSum 這個值出現過幾次，這個次數就等於以當前 node 為終點的有效路徑數量。
• pre[curr] = pre.get(curr, 0) + 1將當前的前綴和 curr 的計數加一。
• 接著count去加遞迴左子樹、右子樹，將子樹中找到的路徑數量累加到當前的 count 中。
• pre[curr] -= 1當 node 的左、右子樹都探索完畢，我們要「離開」node 返回到其父節點時，必須將 node 的前綴和記錄從哈希表中移除。這確保了這條路徑的記錄，不會影響到 node 的兄弟節點所在的其他分支的計算。
• 最後 return count，答案就得知了。

複雜度分析:

• 時間複雜度為 O(n)。

  1. 對樹進行了一次完整的 DFS 遍歷，每個節點只會被訪問一次。
  2. 在每個節點中，對哈希表的操作（查找、插入、刪除）平均時間都是 O(1)。

• 空間複雜度： O(n) (n是樹的高度。空間主要消耗在遞迴呼叫的堆疊，以及哈希表中)。

方法一的執行時間為478ms，方法二可以優化至2ms，是不是差很多呢!
有問題可以底下留言!