一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1192|回复: 13
收起左侧

[CareerCup] 【第三轮】7.14-7.20 CareerCup 4.9

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-7-15 08:35:36 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。

grassgigi 发表于 2014-7-15 10:19:38 | 显示全部楼层
【解题思路】
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
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-15 11:29:55 | 显示全部楼层
【解题思路】
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

回复 支持 反对

使用道具 举报

pyemma 发表于 2014-7-15 11:40:11 | 显示全部楼层
【解题思路】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】
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-18 07:14:33 | 显示全部楼层
【解题思路】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
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-18 11:56:58 | 显示全部楼层
本帖最后由 renli3000 于 2014-7-18 12:29 编辑

【解题思路】这道题一开始我考虑吧所有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
补充: 看了楼上各位的思路,果然还是倒着找比较快啊...智商面壁去了
回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-19 04:18:12 | 显示全部楼层
【解题思路】
遍历每个点和其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
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-19 09:25:08 | 显示全部楼层
【解题思路】
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
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-19 09:56:00 | 显示全部楼层
【解题思路】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
回复 支持 反对

使用道具 举报

tonygxxx1212 发表于 2014-7-19 23:29:56 | 显示全部楼层
【解题思路】注释比较详尽,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
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-22 01:18:59 | 显示全部楼层
【解题思路】recursion, if current node key equals to the remaining sum value, return, else check the left and right subtree
second recursion to check each node as root

【时间复杂度】
O(N^2)
【空间复杂度】
O(lgN) for node list to represent the path

【gist link】
https://gist.github.com/bitcpf/8beb7c1e035c08461596
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-23 09:09:29 | 显示全部楼层
【解题思路】
recursively tree traversal, and save the path in the array, calculate the sum from that node, and print the path if equals to target.
【时间复杂度】
O(N*h) h is the height of the tree
【空间复杂度】
O(h)
【gist link】
https://gist.github.com/iwilbert/b42b689943beb2a1d3df
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-8-14 04:26:55 | 显示全部楼层
【解题思路】
DFS recursion, check if the current node is the end of the valid path
【时间复杂度】
   O(nlog(n))
   if balanced tree; or O(n*h)
【空间复杂度】
  O(h)
【gist link】
  https://gist.github.com/JoyceeLee/7a52bbc5937fc1d400c1
回复 支持 反对

使用道具 举报

yyz20002008 发表于 2014-12-16 07:00:31 | 显示全部楼层
请问这道题要不要考虑root作为中间节点的的情况 比如 求sum=21,root=7,root.left=10,root.right=4,返回10,7,4 or 7 10 4作为一个结果。书上只考虑了root左边或右边的从上到下任意点开始,但start anywhere理论上不得包含从左节点到右节点的情况吗?
多谢指教了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 12:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表