l**h 发帖数: 893 | 1 BFS一层层扫下去,每次都检查一下当前节点是不是至少有两个子节点,然后保存当前
最深的candidate? 这样O(N).
有没有更好一点的办法? |
p*****2 发帖数: 21240 | 2
DFS
【在 l**h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : BFS一层层扫下去,每次都检查一下当前节点是不是至少有两个子节点,然后保存当前 : 最深的candidate? 这样O(N). : 有没有更好一点的办法?
|
c********t 发帖数: 5706 | 3 好在哪里?不也要遍历?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : DFS
|
p*****2 发帖数: 21240 | 4
代码简单
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好在哪里?不也要遍历?
|
l*********8 发帖数: 4642 | 5 空间也少吧。DFS平均是O(logn)空间,BFS是O(n)空间
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 代码简单
|
l**h 发帖数: 893 | 6 DFS你是指recursive的版本简单吧,
Iterative的话,post-order那也不容易,当然这题不需要post-order
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 代码简单
|
A*****i 发帖数: 3587 | 7 想知道DFS如果不用recursion,并且iteration不能用stack还有别的方法没? |
p*****2 发帖数: 21240 | 8
确实。
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 空间也少吧。DFS平均是O(logn)空间,BFS是O(n)空间
|
p*****2 发帖数: 21240 | 9
你这思路真可爱。
【在 l**h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : DFS你是指recursive的版本简单吧, : Iterative的话,post-order那也不容易,当然这题不需要post-order
|
p*****2 发帖数: 21240 | 10
morris
【在 A*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 想知道DFS如果不用recursion,并且iteration不能用stack还有别的方法没?
|
A*****i 发帖数: 3587 | 11 这玩意不是把树结构给重排了么……
没有只遍历不修改的东西?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : morris
|
p*****2 发帖数: 21240 | 12
只是临时改一下。有什么问题吗?
【在 A*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这玩意不是把树结构给重排了么…… : 没有只遍历不修改的东西?
|
c********t 发帖数: 5706 | 13 嗯,是的。
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 空间也少吧。DFS平均是O(logn)空间,BFS是O(n)空间
|