[Java 101] 102. Binary Tree Level Order Traversal - Queue

 

Java STL provides ArrayDeque, LinkedList, and PriorityQueue.

- LinkedList maintains the input order.

- ArrayDeque maintains the input order as well. However, ArrayDeque is more efficient in terms of memory than LinkedList. LinkedList, on the other hand, is efficient when we need to remove elements frequently.

- PriorityQueue maintains the natural order of data.

 

For BFS, consider using ArrayDeque: 

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int qLen = q.size();
            for (int i=0; i<qLen; i++) {
                TreeNode node = q.poll();
                temp.add(node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            ret.add(temp);
        }
        return ret;
    }
}