Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. Zigzag level order traversal means visiting all nodes at each level alternatively from left to right and right to left.
Table of Contents
Sample Input:
Tree:
3
/ \
9 20
/ \
15 7
Expected Output:
[
[3],
[20, 9],
[15, 7]
]
In this example, the zigzag level order traversal of the binary tree will give a 2D vector with nodes’ values grouped by level in a zigzag manner.
Time and Space Complexity:
The time complexity of the algorithm is O(n), where ‘n’ is the number of nodes in the binary tree. We need to visit each node once to perform the zigzag level order traversal. The space complexity is O(w), where ‘w’ is the maximum width of the binary tree (i.e., the maximum number of nodes at any level). In the worst case, the space required to store the nodes at the last level can be at most the width of the tree.
C++ solution:
#include <iostream>
#include <vector>
#include <queue>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
std::vector<std::vector<int>> zigzagLevelOrder(TreeNode* root) {
std::vector<std::vector<int>> result;
// Base case: if the root is null, return an empty result
if (root == nullptr) {
return result;
}
// Create a queue to perform level order traversal
std::queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
bool leftToRight = true; // Variable to alternate the direction of traversal
// Perform zigzag level order traversal
while (!nodeQueue.empty()) {
int levelSize = nodeQueue.size();
std::vector<int> currentLevel(levelSize);
// Process all nodes at the current level
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = nodeQueue.front();
nodeQueue.pop();
// Determine the index based on the direction of traversal
int index = leftToRight ? i : levelSize - 1 - i;
currentLevel[index] = node->val;
// Enqueue the left and right children, if they exist
if (node->left) {
nodeQueue.push(node->left);
}
if (node->right) {
nodeQueue.push(node->right);
}
}
// Add the current level to the result
result.push_back(currentLevel);
// Alternate the direction for the next level
leftToRight = !leftToRight;
}
return result;
}
int main() {
// Construct the binary tree for the sample input
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
// Perform the zigzag level order traversal of the binary tree
std::vector<std::vector<int>> zigzagLevelOrderResult = zigzagLevelOrder(root);
// Print the result
std::cout << "Zigzag Level Order Traversal:" << std::endl;
for (const auto& level : zigzagLevelOrderResult) {
std::cout << "[";
for (int i = 0; i < level.size(); ++i) {
std::cout << level[i];
if (i < level.size() - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
}
// Don't forget to free the allocated memory
// ...
return 0;
}
The zigzagLevelOrder function performs the zigzag level order traversal of the binary tree using a queue. It starts from the root node, and at each level, it processes all nodes at that level. The direction of traversal alternates between left to right and right to left using the leftToRight variable. The nodes’ values are grouped in a zigzag manner based on the direction of traversal.
In the given example, the function will correctly perform the zigzag level order traversal of the binary tree, and the output will be as follows:
Zigzag Level Order Traversal:
[3]
[20, 9]
[15, 7]
The time complexity is O(n) as we need to visit each node once, and the space complexity is O(w) due to the maximum width of the binary tree, where ‘w’ is the maximum number of nodes at any level.