Description:
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:
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []Solution in Python:
To solve the problem of returning the zigzag level order traversal of a binary tree’s nodes’ values in Python, we can use a breadth-first search (BFS) approach with a queue. We will use an additional flag to alternate the order of traversal at each level.
Python
from collections import deque
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
# Initialize the result list to store the zigzag levels of the binary tree
result = []
# If the root is null, return an empty list
if not root:
return result
# Initialize a queue to facilitate BFS
queue = deque([root])
# Flag to indicate the direction of traversal, starting from left to right
left_to_right = True
# Continue processing nodes while the queue is not empty
while queue:
# List to store the values of nodes at the current level
level = []
# Get the number of nodes at the current level
level_size = len(queue)
# Process each node at the current level
for _ in range(level_size):
# Remove the front node from the queue
current_node = queue.popleft()
# Add the value of the current node to the level list
level.append(current_node.val)
# If the current node has a left child, add it to the queue
if current_node.left:
queue.append(current_node.left)
# If the current node has a right child, add it to the queue
if current_node.right:
queue.append(current_node.right)
# If the flag is false, reverse the order of the current level
if not left_to_right:
level.reverse()
# Add the current level list to the result list
result.append(level)
# Toggle the direction flag for the next level
left_to_right = not left_to_right
# Return the result list containing the zigzag level order traversal
return resultExplanation:
- Class and Method Definitions:
TreeNode: Defines the structure of a binary tree node withval,left, andrightproperties.Solution: Contains the methodzigzagLevelOrderto perform the zigzag level order traversal.
- Method
zigzagLevelOrder:- Initialization:
result: Stores the final zigzag level order traversal.- If the root is null, return the empty
resultlist as there are no levels to traverse. queue: Facilitates BFS; initialized usingdequewith the root node.left_to_right: A flag to indicate the direction of traversal, starting from left to right.
- Breadth-First Search (BFS) Loop:
- Continue processing while the queue is not empty.
- Initialize a list
levelto store the nodes’ values at the current level. level_size: Stores the number of nodes at the current level.- Processing Each Level:
- For each node in the current level:
- Remove the front node from the queue using
queue.popleft(). - Add the current node’s value to the
levellist. - If the current node has a left child, add it to the queue using
queue.append(current_node.left). - If the current node has a right child, add it to the queue using
queue.append(current_node.right).
- Remove the front node from the queue using
- For each node in the current level:
- After processing all nodes at the current level, check the direction flag:
- If
left_to_rightisFalse, reverse thelevellist. - Add the
levellist to theresultlist. - Toggle the
left_to_rightflag to alternate the direction for the next level.
- If
- Return the Result:
- Once all levels have been processed, return the
resultlist containing the zigzag level order traversal of the binary tree.
- Once all levels have been processed, return the
- Initialization:
This implementation ensures that each level of the tree is processed in order, and the nodes’ values are collected in a zigzag pattern, alternating the direction at each level.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var zigzagLevelOrder = function(root) {
// Initialize the result array to store the zigzag levels of the binary tree
let result = [];
// If the root is null, return an empty array
if (!root) {
return result;
}
// Initialize a queue to facilitate BFS
let queue = [];
queue.push(root);
// Flag to indicate the direction of traversal, starting from left to right
let leftToRight = true;
// Continue processing nodes while the queue is not empty
while (queue.length > 0) {
// Array to store the values of nodes at the current level
let level = [];
// Get the number of nodes at the current level
let levelSize = queue.length;
// Process each node at the current level
for (let i = 0; i < levelSize; i++) {
// Remove the front node from the queue
let currentNode = queue.shift();
// Add the value of the current node to the level array
level.push(currentNode.val);
// If the current node has a left child, add it to the queue
if (currentNode.left) {
queue.push(currentNode.left);
}
// If the current node has a right child, add it to the queue
if (currentNode.right) {
queue.push(currentNode.right);
}
}
// If the flag is false, reverse the order of the current level
if (!leftToRight) {
level.reverse();
}
// Add the current level array to the result array
result.push(level);
// Toggle the direction flag for the next level
leftToRight = !leftToRight;
}
// Return the result array containing the zigzag level order traversal
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
// Initialize the result list to store the zigzag levels of the binary tree
List<List<Integer>> result = new ArrayList<>();
// If the root is null, return an empty list
if (root == null) {
return result;
}
// Initialize a queue to facilitate BFS
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// Flag to indicate the direction of traversal, starting from left to right
boolean leftToRight = true;
// Continue processing nodes while the queue is not empty
while (!queue.isEmpty()) {
// List to store the values of nodes at the current level
List<Integer> level = new ArrayList<>();
// Get the number of nodes at the current level
int levelSize = queue.size();
// Process each node at the current level
for (int i = 0; i < levelSize; i++) {
// Remove the front node from the queue
TreeNode currentNode = queue.poll();
// Add the value of the current node to the level list
level.add(currentNode.val);
// If the current node has a left child, add it to the queue
if (currentNode.left != null) {
queue.offer(currentNode.left);
}
// If the current node has a right child, add it to the queue
if (currentNode.right != null) {
queue.offer(currentNode.right);
}
}
// If the flag is false, reverse the order of the current level
if (!leftToRight) {
reverseList(level);
}
// Add the current level list to the result list
result.add(level);
// Toggle the direction flag for the next level
leftToRight = !leftToRight;
}
// Return the result list containing the zigzag level order traversal
return result;
}
// Method to reverse a list of integers
private void reverseList(List<Integer> list) {
int left = 0;
int right = list.size() - 1;
while (left < right) {
// Swap elements at left and right indices
int temp = list.get(left);
list.set(left, list.get(right));
list.set(right, temp);
// Move towards the center
left++;
right--;
}
}
}Solution in C#:
C#
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
// Initialize the result list to store the zigzag levels of the binary tree
IList<IList<int>> result = new List<IList<int>>();
// If the root is null, return an empty list
if (root == null) {
return result;
}
// Initialize a queue to facilitate BFS
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
// Flag to indicate the direction of traversal, starting from left to right
bool leftToRight = true;
// Continue processing nodes while the queue is not empty
while (queue.Count > 0) {
// List to store the values of nodes at the current level
List<int> level = new List<int>();
// Get the number of nodes at the current level
int levelSize = queue.Count;
// Process each node at the current level
for (int i = 0; i < levelSize; i++) {
// Remove the front node from the queue
TreeNode currentNode = queue.Dequeue();
// Add the value of the current node to the level list
level.Add(currentNode.val);
// If the current node has a left child, add it to the queue
if (currentNode.left != null) {
queue.Enqueue(currentNode.left);
}
// If the current node has a right child, add it to the queue
if (currentNode.right != null) {
queue.Enqueue(currentNode.right);
}
}
// If the flag is false, reverse the order of the current level
if (!leftToRight) {
level.Reverse();
}
// Add the current level list to the result list
result.Add(level);
// Toggle the direction flag for the next level
leftToRight = !leftToRight;
}
// Return the result list containing the zigzag level order traversal
return result;
}
}