algoadvance

Leetcode 103. Binary Tree Zigzag Level Order Traversal

Problem Statement

The problem is defined as follows:

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).

Clarifying Questions

  1. Input format:
    • Is it guaranteed that the input will always be a non-empty tree?
    • What should be returned if the tree is empty?

    Answer: Yes, the problem guarantees a non-empty tree, and if the tree is empty, we will return an empty list.

  2. Tree properties:
    • Are there any constraints on the number of nodes?

    Answer: No specific constraints are mentioned, so we assume the tree can have any number of nodes.

Strategy

  1. Breadth-First Search (BFS) Traversal:
    • We’ll utilize a queue to perform level-order traversal.
    • We will also maintain a boolean flag to alternate between left-to-right and right-to-left order for each level.
  2. Data Structures:
    • Use a Queue to facilitate BFS traversal.
    • Use a List<List<Integer>> to store the final zigzag level order traversal.
  3. Algorithm:
    • Initialize a queue, add the root node, and start with the left-to-right order.
    • Iterate while the queue is not empty:
      • For each level, store the current level’s nodes.
      • At the end of each level, append the nodes to the result list. If the current level is supposed to be in reverse order, reverse it before appending.
      • Toggle the direction (left-to-right or right-to-left) for the next level.

Code

import java.util.*;

public 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.add(root);
        boolean leftToRight = true;
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> levelList = new ArrayList<>(levelSize);
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                if (leftToRight) {
                    levelList.add(currentNode.val);
                } else {
                    levelList.add(0, currentNode.val);  // Add to the front if it's right-to-left
                }

                if (currentNode.left != null) {
                    queue.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }
            
            result.add(levelList);
            leftToRight = !leftToRight;  // Toggle the direction
        }
        
        return result;
    }

    // TreeNode definition
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

Time Complexity

This concludes our solution to the zigzag level order traversal of a binary tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI