🚀️🔥️ Java/Kotlin 2 simple BFS approaches, both O(n) time & space
Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Approach 1\nJust do the classic BFS and on every odd distance reverse the iterated level.
# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Approach 1\nJust do the classic BFS and on every odd distance reverse the iterated level. A bit slower, but quite simple.\n\n```kotlin []\nclass Solution {\n    fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {\n        if (root == null) return listOf()\n\n        val queue = LinkedList<TreeNode>()\n        val ans = arrayListOf<List<Int>>()\n        var dist = 0\n        queue.addLast(root)\n\n        while (queue.isNotEmpty()) {\n            val size = queue.size\n            val list = arrayListOf<Int>()\n\n            for (i in 0 until size) {\n                val current = queue.removeFirst()\n                current.left?.let { queue.addLast(it) }\n                current.right?.let { queue.addLast(it) }\n                list.add(current.`val`)\n            }\n            if (dist % 2 == 1) list.reverse()\n            ans.add(list)\n            dist++\n        }\n\n        return ans\n    }\n}\n```\n```java []\nclass Solution {\n    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        Queue<TreeNode> queue = new LinkedList<>();\n        List<List<Integer>> ans = new ArrayList<>();\n        int dist = 0;\n        queue.add(root);\n\n        while (!queue.isEmpty()) {\n            int size = queue.size();\n            List<Integer> list = new ArrayList<>();\n\n            for (int i = 0; i < size; i++) {\n                TreeNode current = queue.poll();\n\n                if (current.left != null) queue.add(current.left);\n                if (current.right != null) queue.add(current.right);\n                list.add(current.val);\n            }\n            if (list.isEmpty()) break;\n            if (dist % 2 == 1) Collections.reverse(list);\n            ans.add(list);\n            dist++;\n        }\n\n        return ans;\n    }\n}\n```\n\n# Approach 2\nThere goes some linked list magic. We can use different ends for even/odd levels and then just read the opposite end each time.\n\nSteps:\n1. Add root to LL\n2. Then in while loop: if the current dist is even, do the classic - remove from top, insert to last (left, then right child)\n3. if the current dist is odd, then remove from end of list and insert to first (right, then left since we go in reverse)\n\n```kotlin []\nclass Solution {\n    fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {\n        if (root == null) return listOf()\n\n        val queue = LinkedList<TreeNode>()\n        val ans = arrayListOf<List<Int>>()\n        var dist = 0\n        queue.addLast(root)\n\n        while (queue.isNotEmpty()) {\n            val size = queue.size\n            val list = arrayListOf<Int>()\n\n            for (i in 0 until size) {\n                if (dist % 2 == 0) {\n                    val current = queue.removeFirst()\n\n                    current.left?.let { queue.addLast(it) }\n                    current.right?.let { queue.addLast(it) }\n                    list.add(current.`val`)\n                } else {\n                    val current = queue.removeLast()\n\n                    current.right?.let { queue.addFirst(it) }\n                    current.left?.let { queue.addFirst(it) }\n                    list.add(current.`val`)\n                }\n            }\n\n            ans.add(list)\n            dist++\n        }\n\n        return ans\n    }\n}\n```\n```java []\nclass Solution {\n    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        List<List<Integer>> ans = new ArrayList<>();\n\n        if (root == null) return ans;\n\n        LinkedList<TreeNode> queue = new LinkedList<>();\n        int dist = 0;\n        queue.add(root);\n\n        while (!queue.isEmpty()) {\n            int size = queue.size();\n            List<Integer> list = new ArrayList<>();\n\n            for (int i = 0; i < size; i++) {\n                if (dist % 2 == 0) {\n                    TreeNode current = queue.removeFirst();\n\n                    if (current.left != null) queue.addLast(current.left);\n                    if (current.right != null) queue.addLast(current.right);\n                    list.add(current.val);\n                } else {\n                    TreeNode current = queue.removeLast();\n\n                    if (current.right != null) queue.addFirst(current.right);\n                    if (current.left != null) queue.addFirst(current.left);\n                    list.add(current.val);\n                }\n            }\n\n            ans.add(list);\n            dist++;\n        }\n\n        return ans;\n    }\n}\n```\n\n
['Linked List', 'Breadth-First Search', 'Java', 'Kotlin']