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

题目 #

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表。

返回一个包含所有深度的链表的数组。

思路 #

层序遍历变体

代码 #

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
class Solution {
    public ListNode[] listOfDepth(TreeNode tree) {
        /* 用queue存储单链表头节点，而后将queue转为ListNode[] */
        Queue<ListNode> ansQueue = new LinkedList<>();
        
        /* 二叉树的层序遍历 */
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(tree);
        while (queue.size() != 0) {
            int layerSize = queue.size();
            ListNode sentinel = new ListNode(-1), ptr = sentinel;
            
            for (int i = 0; i < layerSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                ptr = ptr.next = new ListNode(node.val);
            }
            
            ansQueue.offer(sentinel.next);
        }
        
        ListNode[] ans = new ListNode[ansQueue.size()];
        /** 这里如果用 ans[i] = ansQueue.poll(); 则无法通过力扣 ???*/
        int i = 0;
        for (ListNode node: ansQueue) ans[i++] = node;
        return ans;
    }
}