題目網址：https://leetcode.cn/problems/path-sum-iii/

題意：給一 BT 的 root 和一整數 targetSum,　返回路徑總和等於 targetSum 的 path 個數。

path 不需從 root 開始, 也不需在 leaf 結束, 但 path 方向須是向下的（只能從父節點到子節點）。

Solution 1：

想法：利用 DFS

  • traverse() 負責 DFS 遍歷整個 BT
  • countPath(root) 負責計算在 root 為 root 的 BT 中, 以 root 為開頭，且和為 targetSum 的 path 個數
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        int res = 0;
        traverse(root, targetSum, res);
        return res;
    }

private:
    // 遍歷整個 BT
    void traverse(TreeNode* node, long targetSum, int& res){
        if (!node) {
            return;
        }

        countPath(node, targetSum, res);
        traverse(node->left, targetSum, res);
        traverse(node->right, targetSum, res);
    }

    // 計算以 node 為開頭, 且和為 targetSum 的 path 個數
    void countPath(TreeNode* node, const long targetSum, int& res){
        if (node->val == targetSum) {
            ++res;
        }

        // node->val 可以為負數, 所以繼續遍歷其左右子樹
        if (node->left) {
            countPath(node->left, targetSum - node->val, res);
        }

        if (node->right) {
            countPath(node->right, targetSum - node->val, res);
        }
    }
};
  • time：$O(n^2)$
    • $O(n)$：traverse() 遍歷 BT 中所有 node
    • $O(n)$：每個 node 呼叫 countPath() 需 $O(n)$, 因為 worse case 為 skew tree
  • space：$O(n)$ ➔ 遞迴深度不超過 n

Solution 2：

想法：利用 DFS + Prefix Sum + Backtracking

prefix sum 的定義：root 到該點的 path 之和

  • node 4 的 prefix sum 為：1 + 2 + 4
  • node 8 的 prefix sum 為：1 + 2 + 4 + 8

prefix sum 的用途：兩節點之間的 path 和 = 兩節點的 prefix sum 之差

e.g. 以下圖為例

  • node 1 之 prefix sum：1
  • node 3 之 prefix sum：1 + 2 + 3 = 6
  • prefix(3) - prefix(1) = 5, 代表 node 1 和 node 3 之間存在一條和 = 5 的 path (2 ➔ 3)

➔ 我們只需遍歷整棵 tree 一次, 記錄每個 node 的 prefix sum, 並查詢該 node 的 ancestor 中符合條件的個數, 將這些數量加到 res 上

hash table 儲存的是什麼?
hash table 的 key 是 prefix sum, 而 value 是該 prefix sum 的 node 數量, 記錄數量是因為有可能多個 node 擁有一樣的 prefix sum。

e.g. 下圖中, prefix sum = 1 的 node 有兩個 (1, 0)

➔ hash table 初始化為 {0, 1} 代表 prefix sum = 0 的 path 為一條, 因為當 tree 中只有一個 node 時, 且該 node.val 恰為 targetSum 時, res 應返回 1。

恢復狀態的意義?
因為題目要求只能從父節點到子節點, 一個 node 的 prefix sum 加入到 hash table 裡時, 只應對其 child node 有效。因此當遍歷完一個 node 的所有 child node, 並要返回其 parent node 時, 應恢復原先的狀態。

e.g. 下圖中, 假設 targetSum = 8, 當我們遍歷到最右方的 6 時, 此時的符合的 path 只應有 0 ➔ B ➔ 6 和 B ➔ 6 這兩條, 因為從 A 向下到不了 6。

如果我們不做狀態恢復, 當遍歷右子樹時, 左子樹中 A 的 perfix sum 仍會保留在 hash table 中, 此時 6 就會認為 A 和 B 都是可追溯到的 node, 而把 A ➔ 0 ➔ B ➔ 6 也當成合法路徑, 從而產生錯誤。

e.g. 下圖中, 假設 targetSum = 2, 當遍歷到 2 時, 此時 prefix = {1, 2}
➔ 其 ancestor 中 prefix sum = 1 的 node 有兩個(1, 0)
計算 prefix(2) = curSum = 1 + node.val = 3
res = 0 + prefix[3-2] = prefix[1] = 2, 代表有兩個 node 到 2 之間的 path 為 targetSum
➔ 1, 0 之間分別存在一條 path 到 2 為 targetSum (分別是 0 ➔ 2, 2)

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        prefix[0] = 1; // 初始化 prefix sum = 0 的 path 為一條
        return dfs(root, 0, targetSum);
    }

private:
    unordered_map<long, int> prefix; // {prefix_sum : path_num}

    int dfs(TreeNode* node, long curSum, const int targetSum){
        if (!node) {
            return 0;
        }

        int res = 0;
        curSum += node->val;
        res += prefix[curSum - targetSum];

        ++prefix[curSum];
        res += dfs(node->left, curSum, targetSum);
        res += dfs(node->right, curSum, targetSum);
        --prefix[curSum];

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷整個 BT
  • space：$O(n)$ ➔ prefix 和遞迴深度皆不超過 n