前言

今天這題也是TOP 100 Liked中的題目─437. Path Sum III，是昨天最後提到可以延續該題的概念，有一些變化的題目。建議可以先看看昨天的解題想法，再接續這題~

想法

看到題目有什麼想法呢？因為做過昨天的題目，所以我第一個想法就是把每一條path視為一條vector去找subarray，就變成跟前一題一樣了。
而要把每一條path列出來，就可以用dfs的方式，每到一個節點就分像去兩子樹，recursive去探索兩邊子樹到底。而為了要用recursive，我另外就建了一個function來進行搜尋，最初的程式碼如下。
簡單說明：我建立targetCnt這個function來進行recursive，傳入目前節點指標、cumulative sum的次數table、目標sum與目前答案個數，與目前的累積sum，然後計算目前該點的cumulative sum後檢查有無答案加入，然後再新增目前的cumulative sum至次數table，接著若有左右子樹存在，就接續傳入recursive，這樣會實現dfs效果，遍歷到底。

注意：這份程式碼的所需時間、空間都很大，下面會說明原因

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void targetCnt(TreeNode* cur, unordered_map<int, int> acc, int targetSum, int &ans, int curSum){
        curSum += cur->val;
        ans+=acc[curSum-targetSum];
        ++acc[curSum];
        if(nullptr!=cur->left){
            targetCnt(cur->left, acc, targetSum, ans, curSum);
        }
        if(nullptr!=cur->right){
            targetCnt(cur->right, acc, targetSum, ans, curSum);
        }
    }
    int pathSum(TreeNode* root, int targetSum) {
        if(nullptr==root){
            return 0;
        }
        int ans=0;
        // a map to record accumulated sum counts
        unordered_map<int, int> acc;
        acc[0] = 1; // initial state
        int curSum = 0;
        targetCnt(root, acc, targetSum, ans, curSum);
        return ans;
        
    }
};

雖然採用了時間複雜度為O(n)的方式，但這份程式碼要跑很久，關鍵點就在於recursive的呼叫function時，我不斷地傳入了(TreeNode* cur, unordered_map<int, int> acc, int targetSum, int &ans, int curSum)這5個參數，其中撇除cur為指標，targetSum, curSum為 int，空間不大，ans我以傳參考的方式，代表我在function內對answer的改動也會影響到原先傳入的變數的值，因此大家是共享同一個位址內的ans。關鍵在於我的unordered_map，是直接以傳值的方式，這樣每傳一次我的function內就會去複製再建立一個一樣的unordered_map，浪費時間與空間。
比較好的做法就是像ans一樣用傳參考的方式，直接都共用一個unordered_map。不過這樣的用法就要注意，因為在function內的改動就會改動到同一個物件，因此在遍歷完該節點要返回父節點的時候，要記得把新增的count table內的值減回去。修正後程式碼如下，效率了許多；另外也把對nullptr的判斷改到function一開始的檢查，減少一些duplicated code：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void targetCnt(TreeNode* cur, unordered_map<int, int> &acc, int targetSum, int &ans, int curSum){
        if(nullptr==cur){
            return;
        }
        curSum += cur->val;
        ans+=acc[curSum-targetSum];
        ++acc[curSum];
        targetCnt(cur->left, acc, targetSum, ans, curSum);
        targetCnt(cur->right, acc, targetSum, ans, curSum);
        --acc[curSum];
    }
    int pathSum(TreeNode* root, int targetSum) {
        int ans=0;
        // a map to record accumulated sum counts
        unordered_map<int, int> acc;
        acc[0] = 1; // initial state
        int curSum = 0;
        targetCnt(root, acc, targetSum, ans, curSum);
        return ans;
        
    }
};

結語

這兩題之間的變化運用還蠻有趣的，明天再接續來做sum系列的題目好了~