LeetCode: 103. Binary Tree Zigzag Level Order Traversal

The Problem

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

Example

Input:  [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    zigzagLevelOrder(root, ans, 0, true);
    return ans;
}

void zigzagLevelOrder(TreeNode* &root, vector<vector<int>> &ans, int level, bool inverse) { 

    if(root == NULL) return;
    int nextLevel = level + 1;

    if(ans.size() < nextLevel) ans.resize(nextLevel);

    if(inverse) ans[level].push_back(root->val);
    else ans[level].insert(ans[level].begin(), root->val);

    inverse = !inverse;        
    zigzagLevelOrder(root->left, ans, nextLevel, inverse);
    zigzagLevelOrder(root->right, ans, nextLevel, inverse);

}

Here's a breakdown of the code:

1. The zigzagLevelOrder function is the public entry point for the zigzag-level order traversal. It takes the binary tree's root node as input and initializes an empty vector of vectors (ans) to store the result.

2. It calls the helper function zigzagLevelOrder (the second function with the same name) to perform the traversal. The level argument is initially set to 0, indicating the root level, and the inverse argument is initially set to true, indicating that the first level should be traversed from left to right.

3. In the helper zigzagLevelOrder function:

• It checks if the current node (root) is NULL. If it is, it returns immediately, as there's nothing to process for this node.
• It increments the nextLevel variable by 1 to represent the level below the current level.
• It checks if the ans vector has fewer levels than nextLevel. If so, it resizes ans to accommodate the new level.
• Depending on the inverse flag, it either appends the value of the current node (root->val) to the vector corresponding to the current level (ans[level]) or inserts it at the beginning of the vector, effectively reversing the order.
• It toggles the inverse flag to reverse the traversal direction for the next level.
• It recursively calls the zigzagLevelOrder function for the left and right children of the current node, passing nextLevel and the updated inverse value as arguments.

4. The zigzagLevelOrder function is called initially from the public entry point with the root node and an empty ans vector. As the traversal progresses, the ans vector is filled with sub-vectors representing each level of the binary tree, with alternating directions for traversal.

5. Finally, the ans vector, which now contains all the levels of the binary tree in a zigzag pattern, is returned as the result of the zigzag-level order traversal.