103. Binary Tree Zigzag Level Order Traversal – Leetcode Solutions

July 1, 2024

Table of Contents

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 result

Explanation:

Class and Method Definitions:
- TreeNode: Defines the structure of a binary tree node with val, left, and right properties.
- Solution: Contains the method zigzagLevelOrder to 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 result list as there are no levels to traverse.
  - queue: Facilitates BFS; initialized using deque with 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 level to 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 level list.
      - 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).
  - After processing all nodes at the current level, check the direction flag:
    - If left_to_right is False, reverse the level list.
    - Add the level list to the result list.
    - Toggle the left_to_right flag to alternate the direction for the next level.
- Return the Result:
  - Once all levels have been processed, return the result list containing the zigzag level order traversal of the binary tree.

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;
    }
}

103. Binary Tree Zigzag Level Order Traversal – Leetcode Solutions

Description:

Solution in Python:

Explanation:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

181. Employees Earning More Than Their Managers – Leetcode Solutions

133. Clone Graph – Leetcode Solutions

1920. Build Array from Permutation – Solutions

136. Single Number – Leetcode Solutions

166. Fraction to Recurring Decimal – Leetcode Solutions

58. Length of Last Word (String) – Leetcode Solutions

29. Divide Two Integers – Leetcode Solutions

103. Binary Tree Zigzag Level Order Traversal – Leetcode Solutions

Description:

Solution in Python:

Explanation:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular