本文共 2225 字，大约阅读时间需要 7 分钟。

  这道题换个问法，就是二叉树，如何做广度优先遍历。

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。

示例：

输入：[1,2,3,4,5,null,7,8]

        1

       /  \ 

      2    3

     / \    \ 

    4   5    7

   /

  8

输出：[[1],[2,3],[4,5,7],[8]]

在力扣上的测试用例是这样的：

  实际上，题的意思就是，你需要把每层的节点的数字，再构造成链表。这给我带来了很大的困扰。可能我对构造链表没有那么熟悉！

/** * 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) {           }}

看题解：

   1. 先把第一层的一个节点放到辅队列

   2. 对于二叉树的广度优先遍历，我们第一要想要的是使用 队列来辅助完成。

        进入程序循环体，则当前的队列的长度就是此次循环要处理的节点。

              把取到的节点构造成一个链表，用户返回，此时这个链表就是当前层的所有节点

                   把当前节点的左孩子和右兄弟都放到这个辅助的队列里边，用于下轮的遍历

   3. 程序的退出，就是辅助队列里边不再有节点。

/** * 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
   
     queue = new LinkedBlockingQueue<>();		ArrayList
    
      result = new ArrayList<>();		//  生成这个队列		if(tree == null){			return null;		}		queue.add(tree);		while (!queue.isEmpty()){			int point = queue.size();			// 存放当前层，的所有节点的值。			TreeNode tempNode = null;			ListNode head = new ListNode(0);			ListNode nextNode = head;			for (int i = 0; i < point; i++) {				tempNode = queue.poll();				nextNode.next = new ListNode(tempNode.val);				nextNode = nextNode.next;				if(tempNode.left != null){					queue.add(tempNode.left);				}				if(tempNode.right != null){					queue.add(tempNode.right);				}			}			result.add(head.next);		}		return result.toArray(new ListNode[0]);    }}
    
   

这道题的收货

  实际上写的时候，我想到了用队列来辅助。但是要把每层构造成一个链表，这给我带来很大的麻烦，一时没相同，跑不通测试用例。所以链表的知识也应该再巩固一下。

  关于队列，JDK给我们提供的队列里边， ArrayBlockingQueue 构造的时候需要传入一个队列的大小值。 而LinkedBlockingQueue 则不用。

   想要取java中的最大值，可以使用  Integer.MAX_VALUE

算法真的很痛苦~

   痛苦的时候一般在提升吧！

转载地址：http://smsvi.baihongyu.com/