LeetCode 熱題 100 | 437. 路徑總和 III
大家好，今天我們來解決一道經典的二叉樹問題——路徑總和 III。這道題在 LeetCode 上被標記為中等難度，要求計算二叉樹中節點值之和等于給定目標值 targetSum 的路徑數目。
問題描述
給定一個二叉樹的根節點 root，和一個整數 targetSum，求該二叉樹里節點值之和等于 targetSum 的路徑的數目。路徑不需要從根節點開始，也不需要在葉子節點結束，但是路徑方向必須是向下的（只能從父節點到子節點）。
示例 1：
輸入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
輸出：3
解釋：和等于 8 的路徑有 3 條，如圖所示。
示例 2：
輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
輸出：3
提示：
- 二叉樹的節點個數的范圍是
[0, 1000] -10^9 <= Node.val <= 10^9-1000 <= targetSum <= 1000
解題思路
核心思想
-
前綴和：
- 使用前綴和的思想，記錄從根節點到當前節點的路徑和。
- 使用一個哈希表
prefix_sum_count來記錄前綴和出現的次數。
-
遞歸遍歷：
- 遞歸遍歷二叉樹，對于每個節點，計算從根節點到當前節點的路徑和。
- 檢查是否存在一個前綴和，使得當前路徑和減去目標值
targetSum等于該前綴和，如果存在，則路徑數目加一。
-
更新前綴和：
- 在遞歸過程中，更新前綴和的計數。
- 遞歸返回時，恢復前綴和的計數，確保不影響其他路徑的計算。
Python代碼實現
class Solution:def pathSum(self, root: TreeNode, targetSum: int) -> int:from collections import defaultdictdef dfs(node, current_sum):nonlocal countif not node:returncurrent_sum += node.valif current_sum - targetSum in prefix_sum_count:count += prefix_sum_count[current_sum - targetSum]prefix_sum_count[current_sum] += 1dfs(node.left, current_sum)dfs(node.right, current_sum)prefix_sum_count[current_sum] -= 1prefix_sum_count = defaultdict(int)prefix_sum_count[0] = 1count = 0dfs(root, 0)return count
代碼解析
-
初始化：
- 使用
defaultdict初始化前綴和計數器prefix_sum_count，并設置初始值prefix_sum_count[0] = 1。 - 初始化路徑數目
count為 0。
- 使用
-
遞歸函數：
- 定義遞歸函數
dfs，用于遍歷二叉樹并計算路徑和。 - 對于每個節點，更新當前路徑和
current_sum。 - 檢查是否存在一個前綴和，使得當前路徑和減去目標值
targetSum等于該前綴和，如果存在，則路徑數目加一。 - 更新前綴和的計數。
- 遞歸調用
dfs，分別處理左子樹和右子樹。 - 遞歸返回時，恢復前綴和的計數。
- 定義遞歸函數
-
主函數：
- 調用
dfs(root, 0)，從根節點開始遍歷。 - 返回路徑數目
count。
- 調用
復雜度分析
- 時間復雜度：O(n)，其中
n是二叉樹的節點數。每個節點被訪問一次。 - 空間復雜度：O(n)，哈希表
prefix_sum_count的大小最多為n，遞歸調用棧的深度最多為樹的高度。
示例運行
示例 1
輸入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
輸出：3
示例 2
輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
輸出：3
總結
通過前綴和的思想，我們可以高效地計算二叉樹中節點值之和等于目標值的路徑數目。遞歸遍歷二叉樹，使用哈希表記錄前綴和的出現次數，從而快速判斷是否存在滿足條件的路徑。希望這篇題解對大家有所幫助，如果有任何問題，歡迎在評論區留言討論！
關注我，獲取更多算法題解和編程技巧！
