/**

 * 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>> result = new ArrayList< >();

        Queue<TreeNode> queue = new LinkedList<>();

        if(root == null)

        {

            return result;

        }

        queue.add(root);

        boolean flag = true;

        while (!queue.isEmpty())

        {

            int i=0;

            List<Integer> tempList = new ArrayList<>();

            int count = queue.size();

            while (i<count) {

                TreeNode Node = queue.poll();

                tempList.add(Node.val);

                    if (Node.left != null) {

                        queue.add(Node.left);

                    }

                    if (Node.right != null) {

                        queue.add(Node.right);

                    }

                i++;

            }

            if(flag==false)

            {

                Stack<Integer> tempstack = new Stack<>();

                for (Integer tem: tempList

                     ) {

                    tempstack.push(tem);

                }

                List<Integer> list2 = new ArrayList<>();

                while (!tempstack.isEmpty())

                {

                    list2.add(tempstack.pop());

                }

                result.add(list2);

            }

            else

            {

                result.add(tempList);

            }

            flag=!flag;

        }

       return result;

    }

}