題⽬描述

給定⼀個⼆叉樹root和⼀個整數值 sum ，求該樹有多少路徑的的節點值之和等於 sum 。

1. 該題路徑定義不需要從根節點開始，也不需要在葉⼦節點結束，但是⼀定是從⽗親節點往下到孩⼦節點
2. 總節點數⽬為 n
3. 保證最後返回的路徑個數在整形範圍內

假如⼆叉樹 root 為 {1,2,3,4,5,4,3,#,#,-1} ， sum=6 ，那麼總共如下所示，

思路及解答

雙重遞歸法（暴力解法）

外層遞歸遍歷所有節點作為起點，內層遞歸計算從該點向下的路徑和

public class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        
        // 以當前節點為起點的路徑數 + 左右子樹的路徑數
        return countPaths(root, targetSum) + 
               pathSum(root.left, targetSum) + 
               pathSum(root.right, targetSum);
    }
    
    /**
     * 計算以當前節點為起點的路徑數
     */
    private int countPaths(TreeNode node, long targetSum) {
        if (node == null) return 0;
        
        int count = 0;
        
        // 如果當前節點值等於目標值，找到一條路徑
        if (node.val == targetSum) {
            count++;
        }
        
        // 遞歸計算左右子樹
        count += countPaths(node.left, targetSum - node.val);
        count += countPaths(node.right, targetSum - node.val);
        
        return count;
    }
}

• 時間複雜度：O(n²)，最壞情況下每個節點都要遞歸遍歷其子樹
• 空間複雜度：O(n)，遞歸棧深度

前綴和哈希表（最優解）

從根節點到當前節點的路徑和curSum，查找curSum-targetSum是否存在

前綴和核心思想：

• 路徑和 = 當前前綴和 - 之前某個前綴和
• curSum - targetSum是否存在於前綴和哈希表中
• 如果存在，説明從那個節點到當前節點的路徑和為targetSum

執行示例（樹[10,5,-3,3,2,null,11,3,-2,null,1]，sum=8）：

從根到節點3：前綴和=10+5+3=18
targetSum=8 → 查找18-8=10是否存在
哈希表中有10（根節點）→ 找到路徑：5->3

import java.util.HashMap;

public class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // 哈希表存儲前綴和及其出現次數
        HashMap<Long, Integer> prefixSum = new HashMap<>();
        prefixSum.put(0L, 1); // 初始前綴和為0，出現1次
        
        return dfs(root, 0, targetSum, prefixSum);
    }
    
    private int dfs(TreeNode node, long curSum, int targetSum, 
                    HashMap<Long, Integer> prefixSum) {
        if (node == null) return 0;
        
        // 計算從根節點到當前節點的前綴和
        curSum += node.val;
        
        // 查找前綴和中是否存在curSum - targetSum
        // 如果存在，説明從那個節點到當前節點的路徑和為targetSum
        int count = prefixSum.getOrDefault(curSum - targetSum, 0);
        
        // 將當前前綴和加入哈希表
        prefixSum.put(curSum, prefixSum.getOrDefault(curSum, 0) + 1);
        
        // 遞歸處理左右子樹
        count += dfs(node.left, curSum, targetSum, prefixSum);
        count += dfs(node.right, curSum, targetSum, prefixSum);
        
        // 回溯：移除當前前綴和，避免影響其他分支
        prefixSum.put(curSum, prefixSum.get(curSum) - 1);
        
        return count;
    }
}

• 時間複雜度：O(n)，每個節點只訪問一次
• 空間複雜度：O(n)，哈希表存儲n個前綴和

記憶化遞歸法

使用記憶化技術緩存計算結果，為每個節點存儲從該節點向下的路徑和計數,優化遞歸效率。

import java.util.HashMap;

public class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        return pathSumHelper(root, targetSum, new HashMap<>());
    }
    
    private int pathSumHelper(TreeNode node, int targetSum, 
                              HashMap<TreeNode, Integer> memo) {
        if (node == null) return 0;
        
        // 如果結果已緩存，直接返回
        if (memo.containsKey(node)) {
            return memo.get(node);
        }
        
        // 計算以當前節點為起點的路徑數
        int count = countFromNode(node, targetSum, 0);
        
        // 遞歸計算左右子樹
        count += pathSumHelper(node.left, targetSum, memo);
        count += pathSumHelper(node.right, targetSum, memo);
        
        // 緩存結果
        memo.put(node, count);
        
        return count;
    }
    
    private int countFromNode(TreeNode node, int targetSum, long currentSum) {
        if (node == null) return 0;
        
        currentSum += node.val;
        int count = 0;
        
        if (currentSum == targetSum) {
            count++;
        }
        
        count += countFromNode(node.left, targetSum, currentSum);
        count += countFromNode(node.right, targetSum, currentSum);
        
        return count;
    }
}

• 時間複雜度：O(n)，每個節點計算一次
• 空間複雜度：O(n)，緩存所有節點結果