content: package lcci0403_list_of_depth;
  
  import java.util.ArrayList;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Queue;
  
  /**
   * 层序遍历。
   *
   * 时间复杂度和空间复杂度均是O(n)，其中n为树中的节点个数。
   *
   * 执行用时：1ms，击败98.68%。消耗内存：37.9MB，击败100.00%。
   */
  public class Solution {
      public ListNode[] listOfDepth(TreeNode tree) {
          if (null == tree) {
              return new ListNode[0];
          }
          List<ListNode> list = new ArrayList<>();
          Queue<TreeNode> queue = new LinkedList<>();
          queue.add(tree);
          while (!queue.isEmpty()) {
              int qSize = queue.size();
              ListNode dummyHead = new ListNode(-1), cur = dummyHead;
              for (int i = 0; i < qSize; i++) {
                  TreeNode now = queue.poll();
                  cur.next = new ListNode(now.val);
                  cur = cur.next;
                  if (null != now.left) {
                      queue.add(now.left);
                  }
                  if (null != now.right) {
                      queue.add(now.right);
                  }
              }
              list.add(dummyHead.next);
          }
          ListNode[] result = new ListNode[list.size()];
          for (int i = 0; i < result.length; i++) {
              result[i] = list.get(i);
          }
          return result;
      }
  }