Java Four Solutions With Explanations
Four solutions can be used to solve this problem that are:\n\n- Deque\n- Queue with Linked List\n- Recursive\n- Double Stack\n\nPlease check below for details.\
Four solutions can be used to solve this problem that are:\n\n- Deque\n- Queue with Linked List\n- Recursive\n- Double Stack\n\nPlease check below for details.\n\n### Solution 1: Deque\n**Idea:**\n- If direction is left->right, poll nodes from end, offer left and right childs to the front\n- If direction is right->left, poll nodes from front, offer right and left childs to the end\n\n**Code:**\n```java\nclass Solution {\n    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        List<List<Integer>> result = new ArrayList<>();\n        if (root == null) {\n            return result;\n        }\n        Deque<TreeNode> deque = new LinkedList<>();\n        deque.offerLast(root);\n        boolean direction = true; // true: left->right, false: right->left\n        while (!deque.isEmpty()) {\n            int length = deque.size(); // Level length\n            List<Integer> line = new ArrayList<>();\n            while (length-- > 0) {\n                TreeNode node = direction ? deque.pollLast() : deque.pollFirst();\n                line.add(node.val);\n                if (direction) {\n                    if (node.left != null) {\n                        deque.offerFirst(node.left);\n                    }\n                    if (node.right != null) {\n                        deque.offerFirst(node.right);\n                    }\n                } else {\n                    if (node.right != null) {\n                        deque.offerLast(node.right);\n                    }\n                    if (node.left != null) {\n                        deque.offerLast(node.left);\n                    }\n                }\n            }\n            direction = !direction;\n            result.add(line);\n        }\n        return result;\n    }\n}\n```\n\n### Solution 2: Queue with Linked List\n**Idea:**\n- Poll nodes from queue\n- If direction is left->right, add values to list\'s tail\n- If direction is right->left, add valus to list\'s head\n\n**Reference:**\n- https://leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/787/discuss/33814/A-concise-and-easy-understanding-Java-solution\n\n**Code:**\n```java\nclass Solution {\n    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        List<List<Integer>> result = new ArrayList<>();\n        if (root == null) {\n            return result;\n        }\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.offer(root);\n        boolean direction = true; // true: left->right, false: right->left\n        while (!queue.isEmpty()) {\n            int length = queue.size(); // Level length\n            List<Integer> line = new LinkedList<>(); // Use linked list so that add(0, node.val) is O(1)\n            while (length-- > 0) {\n                TreeNode node = queue.poll();\n                if (direction) {\n                    line.add(node.val); // Add to tail\n                } else {\n                    line.add(0, node.val); // Add to head\n                }\n                if (node.left != null) {\n                    queue.offer(node.left);\n                }\n                if (node.right != null) {\n                    queue.offer(node.right);\n                }\n            }\n            result.add(line);\n            direction = !direction;\n        }\n        return result;\n    }\n}\n```\n\n### Solution 3: Recursive\n**Idea:**\n- When traversing the tree recursively, keep track of the current visting level (**beginning from 0**)\n- If level is odd, add nodes to the list head\n- If level is even, add nodes to the list tail\n\n**Reference:**\n- https://leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/787/discuss/33815/My-accepted-JAVA-solution\n\n```java\nclass Solution {\n    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        List<List<Integer>> result = new ArrayList<>();\n        zigzagTraverse(root, result, 0); // Level begins from 0\n        return result;\n    }\n    \n    private void zigzagTraverse(TreeNode root, List<List<Integer>> result, int level) {\n        if (root == null) {\n            return;\n        }\n        if (level == result.size()) {\n            result.add(new LinkedList<>()); // Use linked list so that add(0, val) is O(1)\n        }\n        if ((level & 1) == 1) { // Odd level\n            result.get(level).add(0, root.val);\n        } else {\n            result.get(level).add(root.val);\n        }\n        zigzagTraverse(root.left, result, level+1);\n        zigzagTraverse(root.right, result, level+1);\n    }\n}\n```\n\n### Solution 4: Double Stack\n**Idea:**\n- Travese two stacks seperatedly, and add child nodes to the other stack\n- When traversing stack1, push childs left to right\n- When traversing stack2, push childs right to left\n\n**Reference:**\n- https://leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/787/discuss/33904/JAVA-Double-Stack-Solution\n\n```java\nclass Solution {\n    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        List<List<Integer>> result = new ArrayList<>();\n        if (root == null) {\n            return result;\n        }\n        Stack<TreeNode> stack1 = new Stack<>();\n        Stack<TreeNode> stack2 = new Stack<>();\n        stack1.push(root);\n        while (!stack1.isEmpty() || !stack2.isEmpty()) {\n            List<Integer> line = new ArrayList<>();\n            TreeNode node;\n            while (!stack1.isEmpty()) { // Traverse stack1 and push childs to stack2 left to right\n                node = stack1.pop();\n                line.add(node.val);\n                if (node.left != null) {\n                    stack2.push(node.left);\n                }\n                if (node.right != null) {\n                    stack2.push(node.right);\n                }\n            }\n            if (!line.isEmpty()) {\n                result.add(line);\n            }\n            line = new ArrayList<>();\n            while (!stack2.isEmpty()) { // Traverse stack2 and push childs to stack1 right to left\n                node = stack2.pop();\n                line.add(node.val);\n                if (node.right != null) {\n                    stack1.push(node.right);\n                }\n                if (node.left != null) {\n                    stack1.push(node.left);\n                }\n            }\n            if (!line.isEmpty()) {\n                result.add(line);\n            }\n        }\n        return result;\n    }\n}\n```
[]