Java BFS with Deque


  • 1
    M
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        
        if (root == null) {
            return res;
        }
        
        Deque<TreeNode> dq = new LinkedList<>();
        TreeNode last = root;
        TreeNode tmp;
        List<Integer> buf = new ArrayList<>();
        
        // zig = from left
        boolean zig = true;
        
        dq.offerFirst(root);
        
        while (dq.size() > 0) {
            tmp = zig ? dq.pollFirst() : dq.pollLast();
            buf.add(tmp.val);
            
            if (zig) {
                if (tmp.left != null) {
                    dq.offerLast(tmp.left);
                }
                
                if (tmp.right != null) {
                    dq.offerLast(tmp.right);
                }
            }
            else {
                if (tmp.right != null) {
                    dq.offerFirst(tmp.right);
                }
                
                if (tmp.left != null) {
                    dq.offerFirst(tmp.left);
                }
            }
            
            if (tmp == last) {
                res.add(buf);
                buf = new ArrayList<>();
                last = zig ? dq.peekFirst() : dq.peekLast();
                zig = !zig;
            }
        }
        
        return res;
    }
    

    Some key points about this solution.

    1. Use a flag to record the direction.
    2. Enqueue at the right when dequeuing from the left.
    3. Enqueue at the left when dequeuing from the right.
    4. Alternate between 2 and 3.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.