- 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 | Example: |

方法一：

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

1 | class Solution { |

我的代码实现：

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

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

1 | /** |

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 | class Solution { |

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

18ms Fast One Pass C++ Solution

1 | class Solution { |

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

C++ straight forward solution

1 | class 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

1 | class 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.

1 | class SolutionBruteForce(object): |

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 | class Solution(object): |

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:

- node is None

Recursive case:

- node fits in certain path sum.
- node doesn’t meet.

1 | class Solution(object): |