Binary Tree Zigzag Level Order Traversal | Leetcode

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]
]

Confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

---

Solution: Maintain two lists so that we can choose whether to add the nodes from first to last (for odd rows) or from last to first (for even rows). In each top-level loop, add all the children of the current level nodes.

There are several slightly different ways to solve this problem. The algorithm I show here keeps a direction boolean "leftToRight", and swaps the two lists (curList and nextList) for the next iteration.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> answer = new ArrayList<>();
        if (root == null) return answer;
        
        List curList = new ArrayList<>();
        List nextList = new ArrayList<>();
        curList.add(root);
        boolean leftToRight = true;
        
        do {
            List<Integer> list = new ArrayList<>();
            answer.add(list);
            
            if (leftToRight) {
                for (int i = 0; i < curList.size(); i++) {
                    list.add(curList.get(i).val);
                }
            } else {
                for (int i = curList.size() - 1; i >= 0; i--) {
                    list.add(curList.get(i).val);
                }
            }
            
            leftToRight = !leftToRight;
            
            for (TreeNode node: curList) {
                if (node.left != null) nextList.add(node.left);
                if (node.right != null) nextList.add(node.right);
            }
            curList.clear();
            
            List<TreeNode> tmp = curList;
            curList = nextList;
            nextList = tmp;
        } while (!curList.isEmpty());
        
        return answer;
    }
}