# 103 Binary Tree Zig Zag Level Traversal

用z字型的方式traverse binary tree。

Concept:

跟之前的level order traversal差不多，

只是要多一個規則：

奇數的level從右到左，偶數的level從左到右。

用一個queue來記錄目前讀到哪幾個node，

並用int size記錄這個level有幾個node，就知道要從queue poll出幾個node。

設一個boolean order，來判斷現在是要左向右讀還是右向左讀。

每個迴圈讀完當下這個level的node，存進res。

Pseudocode:

Queue q
q.offer(root)
int size = 1
boolean order = true
List<List<Integer>> ans

while(q is not empty)
    List<Integer> tmp
    for(int i=0; i<size; i++)//visit nodes in current level
        TreeNode n = q.poll()
        if current level is an even level 
            tmp.add(n.val)//from left to right
        if current level is an odd level
            tmp.add(0,n.val//from right to left
        put n.left and n.right into q

    res.add(tmp)
    size = q.size()
    order = !order

return res

完整程式碼：

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean order = true;
        int size = 1;

        while(!q.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < size; ++i) {
                TreeNode n = q.poll();
                if(order) {
                    tmp.add(n.val);
                } else {
                    tmp.add(0, n.val);
                }
                if(n.left != null) q.add(n.left);
                if(n.right != null) q.add(n.right);
            }
            res.add(tmp);
            size = q.size();
            order = order ? false : true;
        }
        return res;
    }
}