【第三轮】7.14-7.20 CareerCup 4.9

4.9 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path does not need to start or end at the root or a leaf.

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
遍历每个点和其parent，在sum小于规定值n前把值都放心list中，当sum等于n时就打印列表，继续下个点。若sum大于n，则sum归零，表清空，继续下个点。总之就是倒着找，顺便LS的思路其实和我差不多
【时间复杂度】
O(N^2)(worst)
【空间复杂度】
O(n)
【gist link】
https://github.com/donnice/donnice/blob/master/Q4_9
【Test】
                     5                                                               
                 2                  8                              
           1          4       7                                          
                 3         6   
找14

【解题思路】这道题一开始我考虑吧所有path输入到list里（leetcode类似方法），然后再逐一分析subpath，结果写了半天代码跑出来一看，找到的subpath有重复难以去除。。。
后来一气之下想出了这个方法，我叫它“sumTree”，即这个tree的每一个node的值都是它path上所有node之和
通过post-order就可以把原来的树变成sumTree，接下来只需从node1的subtree中第归搜索到 所有值为 node1.value + sum 的node3，这样从node2 - node3之间的path就是我们要找的，置于具体值，用后一个sum减前一个sum即可，然后把他们塞进list<E>
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist link】https://gist.github.com/Noahsark/6449aa223777978e32eb
补充： 看了楼上各位的思路，果然还是倒着找比较快啊...智商面壁去了

【解题思路】Travel the tree as well as save the node that exist on the path from the root to the current node, calculate the sum from the current node to previous nodes to see if there exist a valid path
【时间复杂度】O(n*h)
【空间复杂度】O(h)
【gist link】
https://gist.github.com/pyemma/44fafb573aaca8a1b331
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】
Find all paths start from root node and ends anywhere
Then recursively call this function on both its left and right subtree

【时间复杂度】
O(N^2) in worst case, O(NlgN) on average

【空间复杂度】
regardless of recursion depth, O(lgN) for node list to represent the path

【gist link】
https://gist.github.com/chrislukkk/be1ffddf2aff327f33a8

【解题思路】
Traverse every node by level order
exam all paths which terminate at this node
if the sum of the path equals the target value, add it to the final results or print it out.


【时间复杂度】
O(n * h)

【空间复杂度】
O(h)



【gist link】
https://gist.github.com/happyWinner/da099e6d43cecb258bc2

【解题思路】For every node, record the path from root to the node. With the path, we need to find all subpaths that end with this node and sum to the target.
【时间复杂度】O(n*logn)
【空间复杂度】O(logn)
【gist link】https://gist.github.com/jyhjuzi/6e9670d8ab016343cc07

【解题思路】
keep track of the path from root for each node, search its path to see whether it completes a path with the given sum.
【时间复杂度】
O(NlogN)
【空间复杂度】
O(logN)
【gist link】
https://gist.github.com/c522bed2cfbac56bce1e
【test case】
consider following cases:
no match (including sum = 0)
unique match
multiple match

【解题思路】recurse each node from root to n, adds the nodes along path in reverse order from n to root.
【时间复杂度】o(nlogn)
【空间复杂度】o(logn)
【gist link】https://gist.github.com/hilda8519/b1c2e0971ddffbaf0597

【解题思路】注释比较详尽，start from root 和 start form anywhere 都写了， 区别就是是否把 if condition从 for循环 拿出来。其他递归结构都一样。
【时间复杂度】o(nlogn) for start from anywhere, O(logn) for start from root
【空间复杂度】o(logn) 用数组来记录，subsrcript用的是节点的level
【gist link】https://gist.github.com/xun-gong/cf088833764657b0a7d8