437. Path Sum III

发表于 | 更新于: | 分类于 | 本文总阅读量 次
| 字数统计: 1,606 | 阅读时长 ≈ 10
  • 38.9%

https://leetcode.com/problems/path-sum-iii/?tab=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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

方法一：

每一个根节点，一个方向是依照此根节点为一个节点，找到sum。另一个是不含此根节点，寻找下一个根节点为出发点的和。下一个类似于此根节点

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
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        int ans = 0;
        go(root, sum, ans);
        return ans;
    }
    
    void go(TreeNode *root, int need, int &res){
        if(!root)
            return;
        go2(root, need - root->val, res);
        go(root->left, need, res);
        go(root->right, need, res);
    }
    
    void go2(TreeNode *root, int need, int &res){
        if(!root)
            return;
        if(!need)
            res++;
        if(root->left) go2(root->left, need - root->left->val, res);
        if(root->right) go2(root->right, need - root->right->val, res);
    }
    
};

我的代码实现：

第一个函数visit，表示遍历，遍历到root的每个节点

每个节点都有一个从该节点为开始，至一定节点的路径要判断，所以用helper函数。

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
/**
 * 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 {
public:
    int pathSum(TreeNode* root, int sum) {
        int res = 0;
        visit(root, sum, res);
        return res;
    }
    
    void visit(TreeNode* root, int need, int& res){
        if(!root)
            return;
        helper(root, need, res);
        visit(root->left, need, res);
        visit(root->right, need, res);
    }
    
    void helper(TreeNode* root, int need, int& res){
        if(!root)
            return;
        if(need==root->val)
            res += 1;
        helper(root->left, need-root->val, res);
        helper(root->right, need-root->val, res);
    }
};

https://discuss.leetcode.com/topic/64402/c-5-line-body-code-dfs-solution

C++ 5 Line Body Code DFS Solution

For tree structure problems. recursion is usually intuitive and easy to write. lol

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        return sumUp(root, 0, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
    }
private:
    int sumUp(TreeNode* root, int pre, int& sum){
        if(!root) return 0;
        int current = pre + root->val;
        return (current == sum) + sumUp(root->left, current, sum) + sumUp(root->right, current, sum);
    }
};

https://discuss.leetcode.com/topic/64414/18ms-fast-one-pass-c-solution

18ms Fast One Pass C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    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;
    }

    int pathSum(TreeNode* root, int sum) {
        unordered_map<int, int> store;
        return help(root, sum, store, 0);
    }
};

https://discuss.leetcode.com/topic/64438/c-straight-forward-solution

C++ straight forward solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        int res = 0;
        pathSumHelper(root, sum, res, false);
        return res;
    }
    void pathSumHelper(TreeNode* root, int sum, int &res, bool parent_used) {
        if (!root)
            return;
        if (sum - root->val == 0)
            res++;
        pathSumHelper(root->left, sum - root->val, res, true);
        pathSumHelper(root->right, sum - root->val, res, true);
        if (parent_used == false) { //if parent is part of the sum, then we cannot start a new path which jump over this node
            pathSumHelper(root->left, sum, res, false);
            pathSumHelper(root->right, sum, res, false);
        }
    }
};

For tree structure problems. recursion is usually intuitive and easy to write. lol

https://discuss.leetcode.com/topic/64402/c-5-line-body-code-dfs-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        return sumUp(root, 0, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
    }
private:
    int sumUp(TreeNode *root, int pre, int&sum){
        if(!root) return 0;
        int current = pre + root->val;
        return (current == sum) + sumUp(root->left, current, sum) + sumUp(root->right, current, sum);
    }
};

https://discuss.leetcode.com/topic/65100/python-solution-with-detailed-explanation

Python solution with detailed explanation

Path Sum III https://leetcode.com/problems/path-sum-iii/

Brute Force Solution

  • The simplest solution is to traverse each node (preorder traversal) and then find all paths which sum to the target using this node as root.
  • The worst case complexity for this method is N^2.
  • If we have a balanced tree, we have the recurrence: T(N) = N + 2T(N/2). This is the merge sort recurrence and suggests NlgN.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class SolutionBruteForce(object):
    def find_paths(self, root, target):
        if root:
            return int(root.val == target) + self.find_paths(root.left, target-root.val) + self.find_paths(root.right, target-root.val)
        return 0

    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        if root:
            return self.find_paths(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
        return 0

Two Sum Method: Optimized Solution

  • A more efficient implementation uses the Two Sum idea. It uses a hash table (extra memory of order N). With more space, it gives us an O(N) complexity.
  • As we traverse down the tree, at an arbitrary node N, we store the sum until this node N (sum_so_far (prefix) + N.val). in hash-table. Note this sum is the sum from root to N.
  • Now at a grand-child of N, say G, we can compute the sum from the root until G since we have the prefix_sum until this grandchild available.We pass in our recursive routine.
  • How do we know if we have a path of target sum which ends at this grand-child G? Say there are multiple such paths that end at G and say they start at A, B, C where A,B,C are predecessors of G. Then sum(root->G) - sum(root->A) = target. Similarly sum(root->G)-sum(root>B) = target. Therefore we can compute the complement at G as sum_so_far+G.val-target and look up the hash-table for the number of paths which had this sum
  • Now after we are done with a node and all its grandchildren, we remove it from the hash-table. This makes sure that the number of complement paths returned always correspond to paths that ended at a predecessor node.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def helper(self, root, target, so_far, cache):
        if root:
            complement = so_far + root.val - target
            if complement in cache:
                self.result += cache[complement]
            cache.setdefault(so_far+root.val, 0)
            cache[so_far+root.val] += 1
            self.helper(root.left, target, so_far+root.val, cache)
            self.helper(root.right, target, so_far+root.val, cache)
            cache[so_far+root.val] -= 1
        return

    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        self.result = 0
        self.helper(root, sum, 0, {0:1})
        return self.result

https://discuss.leetcode.com/topic/64396/easy-recursive-python-7-lines-solution

Easy Recursive Python 7 lines Solution

Similar to #112 and #113, check the whole tree.

The only difference is: Any node can play as start or end in a valid path.

After each visit, use current node as start, and update the “targets” list.

Pass the updated targets and initial target through.

Base case:

  1. node is None

Recursive case:

  1. node fits in certain path sum.
  2. node doesn’t meet.
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def pathSum(self, root, s):
        return self.helper(root, s, [s])

    def helper(self, node, origin, targets):
        if not node: return 0
        hit = 0
        for t in targets:
            if not t-node.val: hit += 1                          # count if sum == target
        targets = [t-node.val for t in targets]+[origin]         # update the targets
        return hit+self.helper(node.left, origin, targets)+self.helper(node.right, origin, targets)
谢谢你，可爱的朋友。