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

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

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

18ms Fast One Pass C++ Solution

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

C++ straight forward solution

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

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.

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.

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.