新鲜面试题-特定深度节点链表

题目介绍：给定一个二叉树，设计一个算法，创建含有某一深度上所有节点的链表。（比如若一棵树深度为D，则会输出D个链表，第i个链表表示深度为i的一层节点的值构成的线性表）

思路1：深搜

在递归搜索时，传入当前点的层数，并按层加入到数组中。注意题目还要求每层节点的顺序是正确的，所以头插法更适合建立链表，后序遍历图即可完成。

代码实现：（见图更清楚哦）

```java

class Solution {

ArrayList arr;

public void dfs(TreeNode now, int lv){

if(lv==arr.size()) arr.add(new ListNode(now.val));

else{

ListNode ln = new ListNode(now.val);

ln.next = arr.get(lv);

arr.set(lv,ln);

}

if(now.right!=null) dfs(now.right,lv+1);

if(now.left!=null) dfs(now.left,lv+1);

}

public ListNode[] listOfDepth(TreeNode tree) {

arr = new ArrayList();

if(tree != null) dfs(tree,0);

return arr.toArray(new ListNode[] {});

}

}

```

复杂度分析：时间复杂度O(n)，空间复杂度O(n)

思路2：广搜

每次搜完一层后，下一次开始搜索时，将搜索次数（也就是队列大小）设置为下一层的节点数量。

代码：

```java

class Solution {

public ListNode[] listOfDepth(TreeNode tree) {

ArrayList ans = new ArrayList();

Queue q = new LinkedList();

if(tree!=null) q.offer(tree);

while(!q.isEmpty()){

int num = q.size();

for(int i=0; i

TreeNode now = q.poll();

if(i==0) ans.add(new ListNode(now.val));

else{

ListNode ln = new ListNode(now.val);

ln.next = ans.get(ans.size()-1);

ans.set(ans.size()-1,ln);

}

if(now.right!=null) q.offer(now.right);

if(now.left!=null) q.offer(now.left);

}

}

return ans.toArray(new ListNode[]{});

}

}

```

复杂度分析：时间复杂度O(n)，空间复杂度O(n)

欢迎扫描图中二维码关注我们的公众号，专注分享原味笔面试算法题解~~~