Binary Tree Zigzag Level Order Traversal

Problem Statement

In the realm of binary trees, the zigzag level order traversal is a slightly complex yet interesting approach to traverse the tree. Essentially, we alternately traverse the levels of the binary tree: the first level is traversed from left to right, the second from right to left, and this pattern alternates for subsequent levels. Given a binary tree, the goal is to produce a list where each sub-list contains values of the tree nodes at each level according to the zigzag sequence.

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:

[]

Constraints

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

Approach and Intuition

To understand how we might approach the zigzag level order traversal, consider the steps and the intuition behind each:

1. Begin by checking if the given binary tree root is null. If it is, the result is an empty list since there are no nodes to traverse.

2. Initialize a queue to help in level-order traversal and a variable to track the left-to-right or right-to-left order.

3. Use a loop to process each level of the tree:

   • Determine the number of nodes at the current level (queue size).
   • For each node:
     • Record its value.
     • Add its left and right children to the queue if they exist.
   • Depending on the current level's order, append the recorded values to the result list as they are or reverse them before appending.

4. After processing all levels, return the result list.

Examples Breakdown

• Example 1:

  • The first level contains [3]. It’s left to right and remains [3].
  • The second level contains [20, 9]. It's right to left, resulting in [20, 9].
  • The third level, again left to right, contains [15, 7].
  • Combined, the output is [[3], [20, 9], [15, 7]].

• Example 2:

  • There’s only one node and one level, directly resulting in [[1]].

• Example 3:

  • With no nodes given, the result is an empty collection [].

Intuitive Takeaways

The zigzag traversal differs from a normal level-order traversal in that it requires toggling the direction of node value aggregation for each level. Efficient use of data structures like a deque can optimize this process. Each level's nodes are processed fully before moving on to the next, vital for maintaining precise order control, crucial for the zigzag pattern.

Solutions

class Solution {
public:
    vector<vector<int>> levelOrderZigzag(TreeNode* root) {
        if (!root) return {};
        vector<deque<int>> intermediate;
        function<void(TreeNode*, int)> traverse = [&](TreeNode* current, int depth) {
            if (depth >= intermediate.size()) {
                intermediate.emplace_back(deque<int>(1, current->val));
            } else {
                if (depth % 2 == 0)
                    intermediate[depth].push_back(current->val);
                else
                    intermediate[depth].push_front(current->val);
            }
            if (current->left) traverse(current->left, depth + 1);
            if (current->right) traverse(current->right, depth + 1);
        };
        traverse(root, 0);
        vector<vector<int>> ordered_results;
        for (auto layer : intermediate) {
            ordered_results.push_back(vector<int>{layer.begin(), layer.end()});
        }
        return ordered_results;
    }
};