题目描述
给定一棵二叉树,设计一个算法,创建含有某一深度上所有节点的链表(比如,若一棵树的深度为 D,则会创建出 D 个链表)。返回一个包含所有深度的链表的数组。
面试题04. 03. 特定深度节点链表
解法 层序遍历
跟层有关,首先想到层序遍历,我们需要在每一层遍历创建好一个链表,最后将链表放入数组中返回。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode[] listOfDepth(TreeNode tree) {
Queue<TreeNode> queue = new LinkedList<>();
List<ListNode> list = new LinkedList<>();
queue.add(tree);
while(!queue.isEmpty()){
int n = queue.size();
//创建链表的头节点,题目中头节点是每层的最左边的树节点
ListNode a = new ListNode(queue.peek().val);
list.add(a);
for(int i = 0 ;i < n ; i++){
tree = queue.remove();
//非头节点的树节点依次链接到上一个节点
if(i != 0){
a.next = new ListNode(tree.val);
//保证下一次循环的时候a是这次循环创建的链表节点
a = a.next;
}
if(tree.left != null){
queue.add(tree.left);
}
if(tree.right != null){
queue.add(tree.right);
}
}
}
//将链表放入数组中,list里存放的是每个链表的头节点
ListNode[] res = new ListNode[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
}