Binary Tree Zigzag Level Order Traversal

• https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Solution 1

We could borrow the solution from Binary Tree Level Order with minor modification by having a boolean value to check if we need to reverse the list.

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList();
    if (root == null) return result;
    Queue<TreeNode> current = new LinkedList<TreeNode>();
    Queue<TreeNode> next = new LinkedList<TreeNode>();

    current.offer(root);
    List<Integer> currentLevel = new ArrayList();
    boolean needChangeOrder = false;

    while (!current.isEmpty()) {
        TreeNode node = current.poll();
        currentLevel.add(node.val);
        if (node.left != null) {
            next.offer(node.left);
        }
        if (node.right != null) {
            next.offer(node.right);
        }

        if (current.isEmpty()) {
            if (needChangeOrder) {
                Collections.reverse(currentLevel);
                needChangeOrder = false;
            } else {
                needChangeOrder = true;
            }
            result.add(new ArrayList(currentLevel));
            currentLevel = new ArrayList();
            current = next;
            next = new LinkedList<TreeNode>(); 
        }
    }

    return result;        
}

Solution 2 : using stack and a boolean flag

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList();
    if (root == null) return result;
    Stack<TreeNode> current = new Stack<TreeNode>();
    Stack<TreeNode> next = new Stack<TreeNode>();

    current.push(root);
    List<Integer> currentLevel = new ArrayList();
    boolean needChangeOrder = false;


    while (!current.isEmpty()) {
        TreeNode node = current.pop();
        currentLevel.add(node.val);
        if (needChangeOrder) {
             if (node.right != null) {
                next.push(node.right);
            }
            if (node.left != null) {
                next.push(node.left);
            }                
        } else {
            if (node.left != null) {
                next.push(node.left);
            }
            if (node.right != null) {
                next.push(node.right);
            } 
        }

        if (current.isEmpty()) {
            needChangeOrder = !needChangeOrder;
            result.add(new ArrayList(currentLevel));
            currentLevel = new ArrayList();
            current = next;
            next = new Stack<TreeNode>(); 
        }
    }

    return result;        
}