题目描述

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

示例一：

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

        1
       /  \ 
      2    3
     / \    \ 
    4   5    7
   /
  8

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

题解

BFS + 队列

这道题就是层序遍历, 然后将每一层的节点各自存储起来. 之前做过类似的题目, 不过这道题的不同点在于每层的节点数值用链表存储, 但是不影响层序遍历的思路.

做层序遍历的题目时我们会用到队列, 先进先出的特点能够正确地模拟出BFS的顺序.

*算法流程: *

*初始化: * 首先创建一个队列, 将根节点入队; 创建一个列表用于存放每一层的链表, 因为不知道一共有多少层, 所以最后再创建题目要求的数组.
循环过程: 当队列为空时跳出循环
1. 每次循环时, 队列中有多少个节点, 那么就说明这一层有多少个节点, int levelLength = queue.size()
2. 为该层创建一个链表
  - 循环遍历该层所有节点, 将每个节点的左右子节点入队, 并存储在链表中
3. 将该层的链表存入列表中
*返回值: * 根据列表大小创建链表数组, 将列表的元素迁移进去

public ListNode[] listOfDepth(TreeNode tree) {
        if (tree == null)
            return new ListNode[0];

        List<ListNode> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(tree);

        while (!queue.isEmpty()) {
            int levelLength = queue.size();
            ListNode listNode = new ListNode(queue.peek().val);
            ListNode cur = listNode;
            for (int i = 0; i < levelLength; i++) {
                TreeNode node = queue.poll();
                if (i!=0){
                    cur.next = new ListNode(node.val);
                    cur = cur.next;
                }
                if (node.left!=null)
                    queue.add(node.left);
                if (node.right!=null)
                    queue.add(node.right);
            }
            ans.add(listNode);
        }

        ListNode[] res = new ListNode[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }