437. Path Sum III

  • 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)
谢谢你,可爱的朋友。