【第四轮】6.28 - 7.4 Career Cup 4.4

4.4 Given a binary tree, design an algorithm which creates a linked list of all thenodes at each depth (e.g., if you have a tree with depth D, you'll have D linkedlists).


请参加活动的童鞋跟帖回复自己的解法，回复请参考以下格式：

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

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

【解题思路】BFS
【时间复杂度】O（n）
【空间复杂度】O（n）
【gist link】
https://gist.github.com/zhangxin0804/4e9d49883041dede9291

【解题思路】BFS + remember last on the level.
【时间复杂度】O（n）
【空间复杂度】O（n）
【gist link】
gist.github.com/frozenfire888/fafdc6603c07ed9079fe

not allowed to reply url :(

【解题思路】
使用Binary Heap 数据结构
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/alikewmk ... epthlinkedlist-java

【解题思路】DFS，同时记住当前层。
【时间复杂度】
O（n）
【空间复杂度】
O（n）
【gist link】https://gist.github.com/iFighting/63e6118dd3000f80b935