力扣.特定深度节点链表(java BFS解法)

Problem: 面试题 04.03. 特定深度节点链表

题目描述

思路

根据题意需要取出二叉树每一层节点组成的链表并将其添加到一个数组中。我们将该要求分解成如下的操作：

1.利用BFS获取二叉树每一层的节点
2.利用链表的尾插法将二叉树每一层的节点添加到该层节点组成的链表中（采用虚拟头节点和尾指针）

解题方法

1.创建ArrayList集合便于存贮每一层节点组成的链表
2.利用BFS算法获取二叉树每一层的节点，在该遍历每一层时，先创建虚拟头节点和尾指针（尾指针初始化指向创建的虚拟头节点），利用尾插法将该层的节点添加到该层的链表中，最后再将虚拟头节的下一个节点添加到ArrayList集合中
3.将ArrayList集合转换为数组并返回

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

/**
 * 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 {
   /**
     * Gets a list of nodes at each level of a tree
     *
     * @param tree the root node of a tree
     * @return ListNode[]
     */
    public ListNode[] listOfDepth(TreeNode tree) {
        if (tree == null) {
            return new ListNode[0];
        }
        List<ListNode> result = new ArrayList<ListNode>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //Add the root node to queue
        queue.add(tree);
        //BFS
        while (!queue.isEmpty()) {
            //Create a dummy node and a tail pointer
            ListNode dummyHead = new ListNode(Integer.MAX_VALUE);
            ListNode tail = dummyHead;
            int curLevelNum = queue.size();
            for (int i = 0; i < curLevelNum; ++i) {
                TreeNode curLevelNode = queue.poll();
                //Adds the nodes of the current layer
                //to the resulting linked list
                tail.next = new ListNode(curLevelNode.val);
                tail = tail.next;
                if (curLevelNode.left != null) {
                    queue.add(curLevelNode.left);
                }
                if (curLevelNode.right != null) {
                    queue.add(curLevelNode.right);
                }
            }
            //Add the LinkedList of the current level
            //to the resulting list
            result.add(dummyHead.next);
        }
        ListNode[] finalResult = new ListNode[result.size()];
        //Convert List to an array of int
        for (int i = 0; i < result.size(); ++i) {
            finalResult[i] = result.get(i);
        }
        return finalResult;
    }
}