Question:

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

  3
 / \
9  20
  /  \
 15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Thinking:

It’s a BFS problem. It’s fine if we need use queue, but because we have to record as a zigzag order, it’s more efficient to use stack. What’s more, we should to notice the order of left and right child.

Solution:

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    int flag = 0;
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    Stack<TreeNode> tempstack = new Stack<TreeNode>();
    if (root == null)
        return res;
    stack.add(root);
    while (!stack.isEmpty() || !tempstack.isEmpty()){
        tempstack = new Stack<TreeNode>();
        List<Integer> tempres = new ArrayList<Integer>();
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            tempres.add(node.val);
            if (flag == 0){
                if (node.left != null){
                    tempstack.add(node.left);
                }
                if (node.right != null){
                    tempstack.add(node.right);
                }
            }
            else{
                if (node.right != null){
                    tempstack.add(node.right);
                }
                if (node.left != null){
                    tempstack.add(node.left);
                }
            }

        }
        res.add(tempres);
        stack.addAll(tempstack);
        flag ^= 1;
    }

    return res;
}