一亩三分地论坛

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

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

[树/链表/图] 关于cc150 4.9的复杂度

[复制链接] |试试Instant~ |关注本帖
窗外一棵树 发表于 2015-8-17 09:23:45 | 显示全部楼层 |阅读模式

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

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

x
搜了一下 以前有人问过这个问题,不过依然没看懂原因啊。。。http://www.1point3acres.com/bbs/thread-106857-1-1.html


原题是:
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.

我把只考虑 从root出发,可以终结在任意点的情况写出来了
https://gist.github.com/leonw007/90dd6e31353ce071e82a

我没理解错的话,这个基本和答案是差不多的吧,等于跑了一遍DFS,时间复杂度是O(N);

那按照题目的意思,再考虑可以从任意点出发,不仅限于root的情况,不是应该对每一个node,运行一遍上述算法吗?那一共有n个node,不该是O(n^2)咩?

为什么答案说是O(n*logn)啊








ericliu03 发表于 2015-8-17 10:57:36 | 显示全部楼层
楼主,我的理解是 从任一点开始并不是把只从根开始的算法在每个点跑一遍
只从根开始的时候,遍历到每个点的时看一下从当前点到根的和是不是等于sum,等于就print
从任一点开始的时候,还是遍历到每个点的时候看一下,但不是看到根的和等不等于sum,而是一个长度为log(n)的循环,依次比较:此点自己的和是否等于sum,此点加此点父是否等于sum,此点加此点父加此点父的父是否等于sum。。。直到root,循环结束,移至下一个点。所以,所有以此点为终点的,和为sum的路径全部被记录下来。
不知道怎么形容说的啰嗦点,总的来说:“不是问‘这个点是否是一个和为sum路径的起点‘,而问‘这个点是否是一个和为sum的路径的终点’’”【1】。
不知道楼主明白没?

【1】cc150第五版,238页

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 窗外一棵树 发表于 2015-8-17 11:07:25 | 显示全部楼层
ericliu03 发表于 2015-8-17 10:57
楼主,我的理解是 从任一点开始并不是把只从根开始的算法在每个点跑一遍
只从根开始的时候,遍历到每个点 ...

谢谢啊 终于搞懂书上那段话是什么意思了
回复 支持 反对

使用道具 举报

ericliu03 发表于 2015-8-17 21:54:04 | 显示全部楼层
窗外一棵树 发表于 2015-8-17 11:07
谢谢啊 终于搞懂书上那段话是什么意思了

明白就好~
回复 支持 反对

使用道具 举报

 楼主| 窗外一棵树 发表于 2015-8-17 23:18:50 | 显示全部楼层

我按照您说的去实现了一下,好像只要稍作改动就好了。还有两个小问题,求指教

1. 这么实现的前提是否是  写TreeNode这个数据结构的时候必须设定parent?
也就是说 对于一个node,除了value,leftNode,rightNode, 还必须有parent这个变量。

2. 默认的打印顺序就由原来的 从头到尾 变成 反方向了对不?


祝早日拿到理想offer~~~
回复 支持 反对

使用道具 举报

ericliu03 发表于 2015-8-18 01:23:24 | 显示全部楼层
三客优

其实说是parent,并不需要真正的去TreeNode 里面找parent变量,书不在手边,就拿你给的代码来说,public static void findSumPath(TreeNode root, int sum, int[] path, int level)函数中,path这个变量记录的就是从根到目前level节点的路径,也就是说 path[level]就是当前节点,而path[level-1]就是此节点的父节点,对不?
明白了这个,打印的问题也就迎刃而解啦

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 窗外一棵树 发表于 2015-8-18 01:43:31 | 显示全部楼层
ericliu03 发表于 2015-8-18 01:23
三客优

其实说是parent,并不需要真正的去TreeNode 里面找parent变量,书不在手边,就拿你给的 ...

原来我之前理解错你的意思啦。。。

我把每个node从自己向root又递归了一遍。。

本来是
  1.                 findSumPath(root.leftNode, sum, path, level+1);
  2.                 findSumPath(root.rightNode, sum, path, level+1);
复制代码
被我改成
  1. findSumPath(root.parent, sum, path, level+1);
复制代码


这是我用parent link修改的代码https://gist.github.com/leonw007/85e469bef6fcaaac9482
所以print结果是个反的。。

太2了哈哈。。  原来只要加个循环就好了  太感谢了~~

回复 支持 反对

使用道具 举报

ericliu03 发表于 2015-8-18 22:31:26 | 显示全部楼层
窗外一棵树 发表于 2015-8-18 01:43
原来我之前理解错你的意思啦。。。

我把每个node从自己向root又递归了一遍。。

哈哈 思想到是一样~明白了就好~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 13:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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