@@ -0,0 +1,1959 @@
+package problems;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.LinkedList;%0Aimport java.util.List;%0A%0A/* %0A Given a binary tree, return the zigzag level order traversal of its nodes' values. %0A (ie, from left to right, then right to left for the next level and alternate between).%0A */%0A%0A/**%0A * Definition for binary tree public class TreeNode %7B int val; TreeNode left;%0A * TreeNode right; TreeNode(int x) %7B val = x; %7D %7D%0A */%0Apublic class ZigzagLevelOrderTraversal %7B%0A%0A    public class TreeNode %7B%0A        int val;%0A        TreeNode left;%0A        TreeNode right;%0A%0A        TreeNode(int x) %7B%0A            val = x;%0A        %7D%0A    %7D%0A%0A    public List%3CList%3CInteger%3E%3E zigzagLevelOrder(TreeNode root) %7B%0A        List%3CList%3CInteger%3E%3E out = new ArrayList%3CList%3CInteger%3E%3E();%0A        if (root == null)%0A            return out;%0A%0A        List%3CTreeNode%3E q = new LinkedList%3CTreeNode%3E();%0A        q.add(root);%0A        TreeNode end = root;%0A        List%3CInteger%3E list = new LinkedList%3CInteger%3E();%0A        boolean go_right = true;%0A%0A        while (q.size() %3E 0) %7B%0A            TreeNode t = q.remove(0);%0A            if (go_right)%0A                list.add(t.val);%0A            else%0A                list.add(0, t.val);%0A%0A            if (t.left != null)%0A                q.add(t.left);%0A            if (t.right != null)%0A                q.add(t.right);%0A            if (t == end) %7B%0A                out.add(list);%0A                if (q.size() == 0)%0A                    break;%0A%0A                list = new LinkedList%3CInteger%3E();%0A                end = q.get(q.size() - 1);%0A                go_right = !go_right;%0A            %7D%0A        %7D%0A        return out;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        ZigzagLevelOrderTraversal zz = new ZigzagLevelOrderTraversal();%0A%0A        TreeNode t1 = zz.new TreeNode(1);%0A        TreeNode t2 = zz.new TreeNode(2);%0A        TreeNode t3 = zz.new TreeNode(3);%0A        t1.left = t2;%0A        t1.right = t3;%0A%0A        System.out.println(zz.zigzagLevelOrder(t1));%0A    %7D%0A%7D%0A

Add Zigzag Level Order Traversal