algoadvance

Leetcode 103. Binary Tree Zigzag Level Order Traversal

Problem Statement

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. Q: Can the tree be empty? A: Yes, the tree can be empty. In such a case, the function should return an empty list.
  2. Q: How large can the tree be (i.e., number of nodes)? A: The constraints are typically reasonable for a tree traversal problem, but you should ensure the solution is efficient enough for large trees with, say, up to 10^4 nodes.
  3. Q: What should be done if only one node exists in the tree? A: If there is only one node, the output should be a list with one sublist containing that single node.

Strategy

  1. Use a breadth-first search (BFS) approach with the help of a queue to traverse the tree level by level.
  2. Use an indicator (leftToRight) to keep track of the current traversal direction (left-to-right or right-to-left).
  3. For each level, collect nodes in a list, and based on the direction indicated by leftToRight, append this list to the result (reverse the list if needed).
  4. Flip the leftToRight indicator after processing each level.

Time Complexity

Code

#include <iostream>
#include <vector>
#include <queue>
#include <deque>

using namespace std;

// 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) {}
};

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;
        
        queue<TreeNode*> nodeQueue;
        nodeQueue.push(root);
        bool leftToRight = true;
        
        while (!nodeQueue.empty()) {
            int size = nodeQueue.size();
            deque<int> currentLevel;
            for (int i = 0; i < size; ++i) {
                TreeNode* currentNode = nodeQueue.front();
                nodeQueue.pop();
                
                if (leftToRight) {
                    currentLevel.push_back(currentNode->val);
                } else {
                    currentLevel.push_front(currentNode->val);
                }
                
                if (currentNode->left != nullptr) {
                    nodeQueue.push(currentNode->left);
                }
                if (currentNode->right != nullptr) {
                    nodeQueue.push(currentNode->right);
                }
            }
            result.push_back(vector<int>(currentLevel.begin(), currentLevel.end()));
            leftToRight = !leftToRight;
        }

        return result;
    }
};

Explanation

  1. Queue Initialization: A queue (nodeQueue) is initialized and the root node is pushed into it if the root is not null.
  2. Traversal: While there are nodes in the queue,
    • Determine the number of nodes at the current level (size).
    • Use a deque (currentLevel) to store the values of nodes at the current level.
    • Iterate through nodes at the current level. If leftToRight is true, append the values to the end of the deque; otherwise, append to the front.
    • Push the left and right children of the current node into the queue if they exist.
  3. Direction Toggle: After finishing traversing a level, toggle the leftToRight flag.
  4. Store Result: Convert the deque to a vector and store it in the result list.

This ensures that each level is properly captured in zigzag manner.

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