[Day 22] Leetcode 437. Path Sum III (C++)

前言

今天这题也是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系列的题目好了~