LeetCode Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

  10
 /  \
5   -3

/ \
3 2 11
/ \
3 -2 1

Return 3. The paths that sum to 8 are:

1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11

解法一：
到达每个结点时，求出以其结尾的所有路径的长度可能性，递归下去的时候便可以根据这些所有的长度求出下一层长度的可能性。每一个结点求出长度可能性之后，都要扫一遍获得有几条满足题意的路径（开销很大）。

    int pathSum(TreeNode* root, int sum) {
        int res = 0;
        vector<int> vec;
        dfs(root, sum, vec, res);
        return res;
    }
    void dfs(TreeNode* root, int sum, vector<int> vec, int& res) {
        if(!root) return;
        vector<int> next;
        next.push_back(root -> val);
        if(root -> val == sum) res++;
        for(int i = 0; i<vec.size(); i++){
            int tmp = vec[i] + root -> val;
            if(tmp == sum) res++;
            next.push_back(tmp);
        }
        dfs(root -> left, sum, next, res);
        dfs(root -> right, sum, next, res);
    }

解法二：
pathSumFrom表示一定以root开始的路径。

    int pathSum(TreeNode* root, int sum) {
        if(root == NULL) return 0;
        return pathSumFrom(root, sum) + pathSum(root -> left, sum) + pathSum(root -> right, sum);
    }
    
    int pathSumFrom(TreeNode* root, int sum) {
        if(root == NULL) return 0;
        return (root->val == sum) + pathSumFrom(root->left, sum - root->val) + pathSumFrom(root->right, sum - root->val);
    }

解法三（完美解法）：
解决了 解法一 中每个结点都要扫一遍的开销问题。使用了一个map记录了以每个结点为结尾的前缀和。

    int pathSum(TreeNode* root, int sum) {
        unordered_map<int, int> mp;
        return dfs(root, sum, 0, mp);
    }
    
    int dfs(TreeNode* root, int sum, int cur, unordered_map<int, int>& mp) {
        if(root == NULL) return 0;
        cur += root->val;
        int res = (cur == sum) + (mp.count(cur - sum) ? mp[cur-sum]: 0);
        mp[cur]++;
        res += dfs(root -> left, sum, cur, mp) + dfs(root -> right, sum, cur, mp);
        mp[cur]--;
        return res;
    }