Back to Trees
Medium
Binary Tree Zigzag Level Order Traversal
Given the `root` of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
Examples
Input:root = [3,9,20,null,null,15,7]
Output:[[3],[20,9],[15,7]]
Input:root = [1]
Output:[[1]]
Constraints
The number of nodes in the tree is in the range [0, 2000].-100 <= Node.val <= 100
Approach
Perform a standard level order traversal using BFS. Keep track of a boolean variable `leftToRight`. After collecting all the node values for a level in a list, if `leftToRight` is false, reverse the collected values for that level before adding it to the result list. Finally, toggle the `leftToRight` variable for the next level.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Reversing a list of size k takes O(k) time, so the total reversal time across all levels is O(n).
Solution.java
class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) return res; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); boolean leftToRight = true; while (!q.isEmpty()) { int levelSize = q.size(); List<Integer> currentLevel = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = q.poll(); currentLevel.add(node.val); if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); } if (!leftToRight) { Collections.reverse(currentLevel); } res.add(currentLevel); leftToRight = !leftToRight; } return res; }}