Java O(n) time O(log n) space | BFS | single Deque | 1ms
The main idea is to \n1. Read from Front : left-to-right\n2. Write to Rear the left child followed by the right child\n3. Read from Rear : right-to-left\n4. Wri
The main idea is to \n1. Read from Front : left-to-right\n2. Write to Rear the left child followed by the right child\n3. Read from Rear : right-to-left\n4. Write to Front the right child followed by the left child\n\nAs each item is removed from either end of the queue it is added to the result list\n![image](https://assets.leetcode.com/users/images/c06f30df-9e15-4abb-ae17-6dc58a0f0e9f_1595413106.21344.png)\n```\npublic List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        if(root==null) {\n            return Collections.emptyList();\n        }\n        \n        ArrayDeque<TreeNode> deque = new ArrayDeque<>();\n\t\tList<List<Integer>> result = new ArrayList<>();\n        List<Integer> row  = null;\n\t\tTreeNode node = null;\n        deque.addFirst(root);\n        \n        while(!deque.isEmpty()) {\n            \n            row = new ArrayList<>();\n            result.add(row);\n            int size = deque.size();\n\t\t\t\n            while(size>0) {\n                node = deque.removeFirst();                \n                row.add(node.val);\n                \n                if(node.left!=null) {\n                    deque.addLast(node.left);\n                }\n                \n                if(node.right!=null) {\n                    deque.addLast(node.right);\n                }\n                \n                size--;\n            }\n            \n            size = deque.size();\n            if(size > 0) {\n                row = new ArrayList<>();\n                result.add(row);\n            }\n            \n            while(size > 0) {\n                node = deque.removeLast();\n                row.add(node.val);\n                \n                if(node.right!=null) {\n                    deque.addFirst(node.right);\n                }\n                \n                if(node.left!=null) {\n                    deque.addFirst(node.left);\n                }    \n                \n                size--;\n            }\n        }\n        return result;\n    }\n```\n\nTime Complexity : **O(n)** \nBecause, each item is put into the queue and read back only once.\nSpace Complexity: **O(log n)** \nBecause, in a complete binary tree for each removal, 2 addition will happen. Thus at any level with m nodes the queue will have at most 2m nodes.\nEg: a complete binary tree with 15 nodes, the queue will have a maximal length of 8 nodes.
['Breadth-First Search', 'Queue', 'Java']