面試題 04.03. 特定深度節點連結清單

層序周遊加虛拟節點

思路

• 使用隊列進行層序周遊
• 虛拟節點

實作代碼

class Solution {
    public ListNode[] listOfDepth(TreeNode tree) {
        ListNode dummy = new ListNode(0);
        LinkedList<TreeNode> queue = new LinkedList<>();
        List<ListNode> res = new ArrayList<>();
        TreeNode root;
        queue.add(tree);
        int size;
        while(!queue.isEmpty()){
            ListNode cur = dummy;
            //這裡記錄目前隊列的大小，不能在for循環中判斷隊列大小 因為for循環中
            //左右孩子存在，隊列會變長
            size = queue.size();
            for(int i = 0; i < size; i++){
                root = queue.remove();
                cur.next = new ListNode(root.val);
                if(root.left != null){
                    queue.add(root.left);
                }
                if(root.right != null){
                    queue.add(root.right);
                }
                cur = cur.next;
            }
            res.add(dummy.next);
        }
        return res.toArray(new ListNode[]{});
    }
}