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