🎨Now live: Try our Free AI Image Generation Feature

Description
This problem involves performing a level-order traversal of a binary tree in a zigzag pattern, alternating directions between levels.
Intuition
To achieve the zigzag traversal:
- Use a queue for level-order traversal.
- Maintain a flag to track the direction (left to right or right to left) for each level.
- Adjust the insertion order of node values based on the direction flag.
Approach
- Initialization: Start with an empty result list and a queue initialized with the root node.
- Level Order Traversal: - Iterate over the nodes in the queue for each level. - Depending on the direction flag, append or insert node values into the current level list. - Enqueue child nodes (left and right) for the next level.
- Direction Control: Toggle the direction flag after processing each level to alternate between left to right and right to left.
- Completion: Once the queue is empty, all levels have been processed. Return the result list containing all levels.
Complexity
Time Complexity:
O(n), where n is the number of nodes in the binary tree. Each node is processed exactly once.
Space Complexity:
O(n), in the worst case (completely unbalanced tree), the queue can contain all nodes at the maximum width of the tree.
Code
C++
class Solution {
public:
vector> zigzagLevelOrder(TreeNode* root) {
if (!root) return {};
vector> result;
queue queueNodes;
queueNodes.push(root);
bool leftToRight = true;
while (!queueNodes.empty()) {
int size = queueNodes.size();
vector level(size);
for (int i = 0; i < size; ++i) {
TreeNode* node = queueNodes.front();
queueNodes.pop();
int index = leftToRight ? i : size - 1 - i;
level[index] = node->val;
if (node->left) queueNodes.push(node->left);
if (node->right) queueNodes.push(node->right);
}
result.push_back(level);
leftToRight = !leftToRight;
}
return result;
}
};
Python
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
result = []
queue = deque([root])
left_to_right = True
while queue:
level_size = len(queue)
level_values = []
for _ in range(level_size):
node = queue.popleft()
if left_to_right:
level_values.append(node.val)
else:
level_values.insert(0, node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_values)
left_to_right = not left_to_right
return result
Java
class Solution {
public List> zigzagLevelOrder(TreeNode root) {
List> result = new ArrayList<>();
if (root == null) return result;
Queue queue = new LinkedList<>();
queue.offer(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int size = queue.size();
List level = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (leftToRight) {
level.add(node.val);
} else {
level.add(0, node.val);
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
leftToRight = !leftToRight;
}
return result;
}
}
JavaScript
var zigzagLevelOrder = function(root)
{
if (!root) return [];
let stackQueue = [root];
let result = [];
let level = 1;
while (stackQueue.length > 0) {
const isLtoR = level % 2 === 1;
const subLength = stackQueue.length;
const subList = [];
for (let i = 0; i < subLength; i++)
{
let node= stackQueue.shift();
if (isLtoR) {
subList.push(node.val);
} else {
subList.unshift(node.val);
}
if (node.left) stackQueue.push(node.left);
if (node.right) stackQueue.push(node.right);
}
level++;
result.push(subList);
}
return result;
};