FXTi's blog
0%

path-sum-iii

Posted on Edited on

Path Sum III – LeetCode 437

Problem

Description

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.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int rootSum(TreeNode* root, int sum) {
        if (!root) return 0;
        return (sum == root->val) + rootSum(root->left, sum - root->val) + rootSum(root->right, sum - root->val);
    }
    
public:
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        return rootSum(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
    }
};

思路

一样是DFS，但要考虑到本节点参与构成加和链和以本节点为首构建加和链的两种情况。时间复杂度$O(n^2)$，空间复杂度$O(n)$。
耗时$21$ ms，排名$50.98\%$

Better

思路

应注意到，这个问题可以看成是在每一条分支上寻找能够构成特定和的连续路径。于是可以借用缓存来加速。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$13$ ms，排名$13.39\%$

Code

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int help(TreeNode* root, int sum, unordered_map<int, int>& store, int pre) {
        if (!root) return 0;
        root->val += pre;
        int res = (root->val == sum) + (store.count(root->val - sum) ? store[root->val - sum] : 0);
        store[root->val]++;
        res += help(root->left, sum, store, root->val) + help(root->right, sum, store, root->val);
        store[root->val]--;
        return res;
    }
    
public:
    int pathSum(TreeNode* root, int sum) {
        unordered_map<int, int> store;
        return help(root, sum, store, 0);
    }
};