0437. 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

算法1

$O(2^n)$

如果可以从任意点开始，那么说明每个位置的node都有可能是start，那么只要这两种情况都过一遍就可以了。 在递归的时候用一个变量as_start代表是否从当前节点开始。

时间复杂度分析：brute force相当于每个节点都尝试一遍，所以对于每个节点都有两个operation，如果有 n个节点，那么一共有2^n种选法。

C++

class Solution {
public:
    int res;
    int pathSum(TreeNode* root, int sum) {
        traverse(root, sum, 0, true);
        return res;
    }
    // there are two choice: 1 start from current node 2. keep going from current node
    void traverse(TreeNode* root, int sum, int curr_sum, bool as_start) {
        if (!root)
            return;
        curr_sum += root -> val;
        if (curr_sum == sum)
            res++;
        traverse(root -> left, sum, curr_sum, false);
        traverse(root -> right, sum, curr_sum, false);
        if (as_start) {
            traverse(root -> left, sum, 0, true); // start from next node, so sum is 0
            traverse(root -> right, sum, 0, true);
        }
    }
};

算法2

$O(n)$ space $O(n)$

第一种复杂度高的原因是每个节点都要判断是否可以作为头节点，这样每个节点相当于都要再跑n次。 但是其实没有必要每次都查，这道题可以想像成two sum。 我们每次存当前到root的sum，这样每次到某个节点我们就只要看超过target的部分是不是已经在之前存在过了（因为是root到当前节点的sum，所以必定是连续的）。 这个map我用m来表示，key是sum的值，value是个数，因为可能存在多个（假如有负数存在）。 two sum那道题其实也是类似的思想，只不过是有两个，所以不用map来存个数，直接用set来看存不存在就可以了。

时间复杂度分析：每个节点只要走一次，但是要牺牲space来存之前的sum，所以space是n，time是n。

C++

class Solution {
public:
    int res;
    unordered_map<int, int> m; // sum: number of ways to form this sum
    int pathSum(TreeNode* root, int sum) {
        if (!root)
            return 0;
        m[0] = 1; // the node before root: value is 0 and it has 1 way to get that sum
        traverse(root, sum, root -> val);
        return res;
    }

    void traverse(TreeNode* root, int sum, int curr_sum) {
        if (!root)
            return;
        // check the complements
        if (m.count(curr_sum - sum))
            res += m[curr_sum - sum];
        m[curr_sum]++;
        if (root -> left)
            traverse(root -> left, sum, curr_sum + root -> left -> val);
        if (root -> right)
            traverse(root -> right, sum, curr_sum + root -> right -> val);

        m[curr_sum]--; // don't forget to set it back
    }
};

---

Last update: April 1, 2022