Cinte's Leetcode Record
0%

437. Path Sum III

Posted on Edited on In Disqus:
Symbols count in article: 3k Reading time ≈ 3 mins.

437. Path Sum III

backTrack

这是对每个点都遍历他的儿子，从而判断路径，时间复杂度为(n^2) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 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:
    int pathSum(TreeNode* root, int targetSum) {
        if(!root)
            return 0;
        stack<TreeNode*> q;
        q.push(root);
        int count = 0;
        int cur = 0;
        while(!q.empty())
        {
            auto p = q.top();
            q.pop();
            backTrack(p, targetSum, cur, count);
            if(p->left)
                q.push(p->left);
            if(p->right)
                q.push(p->right);
        }
        return count;
    }
private:
    void backTrack(TreeNode* root, int target, int& cur, int& count)
    {
        if(!root)
            return;
        cur += root->val;
        if(cur == target)
            ++count;
        backTrack(root->left, target, cur, count);
        backTrack(root->right, target, cur, count);
        cur -= root->val;
    }
};
##### 使用hashmap

记录路径上的和，当 可知 路径中某一段的值 = 当前和 - 某一段开始位置之前的和，由此，target = curSum - somePlaceSum--> somePlaceSum = curSum - target,如果这个值存在于走过的路径上，那么表示存在这一段和=target，由于可能存在不同段具有相同的和，因此进行计数

使用backTrack来记录每一段的hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 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:
    int pathSum(TreeNode* root, int targetSum) {
        if(!root)
            return 0;
        cur += root->val; // 加上当前值，开始遍历他的儿子
        int ret = map[cur - targetSum]; // 如果存在在他回溯的路径上存在cur-targetSum的值，说明存在这样一个节点使得在此节点之前的和为cur-targetSum。如果路径上存在多条和为此，那么后面也和他的路径数量相同。
        ++map[cur]; // 路径当前和所对应的计数加一。可处理存在重复和的情况。
        ret += pathSum(root->left, targetSum) + pathSum(root->right, targetSum); // 往儿子遍历，如果儿子中也存在这样的路径，那就加上去。
        --map[cur]; // 回溯返回
        cur -= root->val; // 回溯返回
        return ret; // 返回这个节点到他儿子路上和为target的路径数
    }
private:
    unordered_map<int, int> map{{0, 1}};
    int cur = 0;
};

时间复杂度为O(n)

review 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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:
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<int, int> map;
        map[0] = 1;
        recurse(root, map, targetSum, 0);
        return ret;
    }
private:
    int ret = 0;
    void recurse(TreeNode* root, unordered_map<int, int>& map, int targetSum, int curSum)
    {
        if(!root)
            return;
        curSum += root->val;
        ret += map[curSum - targetSum]; // 注意这两行的顺序，大坑啊
        ++map[curSum];                  // 如果++在前的话，假如targetSum = 0，那就每个节点都会算上自己了，对于targetSum不是0的情况似乎没什么影响
        recurse(root->left, map, targetSum, curSum);
        recurse(root->right, map, targetSum, curSum);
        --map[curSum];
    }
};