【第三轮】7.7-7.13 CareerCup 4.4

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

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

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

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

【解题思路】先通过遍历每一个节点来判断它们的深度，再把相同深度的node们add进一个linkedlist。要注意高度差不等于深度，因为一棵树的高度是指比较长的分叉的高度，而如果任意左右两叉高度不等，用高度的概念代替深度会出现错误。
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist】
https://github.com/donnice/donnice/blob/master/Q4_4
【Test case】
                       5                                                               
              2                  8                              
        1          4       7                                          
              3         6   

【解题思路】BFS 设置节点属性dep 表示当前节点的深度，TreeNode Next属性表示更改后当前节点下一个节点
BFS 访问二叉树，根节点的dep为1，记录当前深度curdepth；
如果curdepth不等于当前节点的dep说明进入下一层，当前节点是该层头结点加入到list
访问当前节点左子右节点设置左右节点深度
【时间复杂度】O(n)
【空间复杂度】因为每个节点都多了一个Next属性，算作 O(n)
【gist link】https://gist.github.com/Hailen/3a23b7ad2d10e7da5b24
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】  
    2
   / \
  9  10
    /  \
   11   7

【解题思路】
1. get height of the tree, create an array of linked links with size height, recursively traverse the tree and push nodes into corresponding layer of list.
2. similar with 1 but use vector to hold the lists instead of array, do not need to know the height of tree ahead
3. BFS: create each level (exempt the first one) with all children of the nodes from the previous level
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/d1c9fb4b155c2c502c76

【解题思路】
BFS -  level order traversing the tree

【时间复杂度】
O(N)

【空间复杂度】
O(N)

【gist link】
https://gist.github.com/chrislukkk/15bb4a11c3c4872d0e6a

binray tree & tree builder:
https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8

【解题思路】
BFS


【时间复杂度】
O(n)


【空间复杂度】
O(n)


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

【解题思路】BFS tell the depth of each node, add them to a linkedlist, and pull them out according to the layer
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist】https://gist.github.com/bitcpf/bdf67403863da2e86de2

【解题思路】Transverse the tree by layer
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist】https://gist.github.com/nealhu/639b16c2560d62e78fdf

【解题思路】
level order traversal
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist】
https://gist.github.com/JoyceeLee/950b1246427d76a419ed