The Binary Tree Zigzag Level Order Traversal problem asks you to traverse a binary tree in a level-by-level manner, but with a twist: the order alternates between left-to-right and right-to-left at each level.
root node of a binary tree, return its zigzag level order traversal as a list of lists of node values.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
Constraints:
The problem is a variant of the classic level order traversal (also known as breadth-first traversal) of a binary tree. In the standard approach, you process each level from left to right. However, the zigzag requirement means that the direction alternates at each level: left-to-right, then right-to-left, then left-to-right, and so on.
My first thought was to use a queue to perform the level order traversal, as is typical. However, to alternate the direction, I realized I could reverse the list of values for every other level, or collect values in different orders depending on the level.
A brute-force way would be to collect all node values at each level, then reverse the list for every odd-numbered level. But I wondered if there’s a more elegant way, perhaps by using a double-ended queue (deque) or by carefully controlling the order in which children are added to the queue.
Ultimately, the optimized approach is to use a standard queue for BFS, and at each level, either append values normally or in reverse, depending on the current level's parity (even or odd).
Here’s a step-by-step breakdown of the zigzag traversal algorithm:
left_to_right) to keep track of the current direction. Start with True for left-to-right.
level_size).level_nodes) to hold the values of the current level.level_nodes.left_to_right is False, reverse level_nodes before adding it to the result.
level_nodes to the result list.
left_to_right flag for the next level.
Why this works: The queue ensures we process nodes level by level, and the direction flag ensures we alternate the order of values as required. This approach is efficient and easy to implement.
Consider the following binary tree:
1
/ \
2 3
/ \ \
4 5 6
Let’s walk through the traversal step by step:
1. Output: [1]
2 and 3. Output: [3, 2]
4, 5, and 6. Output: [4, 5, 6]
[
[1],
[3, 2],
[4, 5, 6]
]
Notice how the order alternates at each level, producing the desired zigzag pattern.
The Binary Tree Zigzag Level Order Traversal problem is a twist on classic BFS traversal. By using a queue and a direction flag, we can efficiently traverse each level in alternating orders. The approach is elegant because it leverages the natural level-order structure of BFS, requiring only minor modifications to achieve the zigzag pattern. This results in a clear, maintainable, and optimal solution.
from collections import deque
class Solution:
def zigzagLevelOrder(self, root):
if not root:
return []
result = []
queue = deque([root])
left_to_right = True
while queue:
level_size = len(queue)
level_nodes = []
for _ in range(level_size):
node = queue.popleft()
level_nodes.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not left_to_right:
level_nodes.reverse()
result.append(level_nodes)
left_to_right = not left_to_right
return result
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
bool left_to_right = true;
while (!q.empty()) {
int level_size = q.size();
vector<int> level_nodes;
for (int i = 0; i < level_size; ++i) {
TreeNode* node = q.front();
q.pop();
level_nodes.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
if (!left_to_right)
reverse(level_nodes.begin(), level_nodes.end());
result.push_back(level_nodes);
left_to_right = !left_to_right;
}
return result;
}
};
import java.util.*;
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> levelNodes = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
levelNodes.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
if (!leftToRight) {
Collections.reverse(levelNodes);
}
result.add(levelNodes);
leftToRight = !leftToRight;
}
return result;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var zigzagLevelOrder = function(root) {
if (!root) return [];
const result = [];
const queue = [root];
let leftToRight = true;
while (queue.length > 0) {
const levelSize = queue.length;
const levelNodes = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
levelNodes.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
if (!leftToRight) {
levelNodes.reverse();
}
result.push(levelNodes);
leftToRight = !leftToRight;
}
return result;
};