123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
#include <bits/stdc++.h>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
// Vector to store the result of zigzag traversal
vector<vector<int>> result;
// Check if the root is NULL, return an empty result
if (root == nullptr) {
return result;
}
// Queue to perform level order traversal
queue<TreeNode*> nodesQueue;
nodesQueue.push(root);
// Flag to determine the direction of traversal (left to right or right to left)
bool leftToRight = true;
// Continue traversal until the queue is empty
while (!nodesQueue.empty()) {
// Get the number of nodes at the current level
int size = nodesQueue.size();
// Vector to store the values of nodes at the current level
vector<int> row(size);
// Traverse nodes at the current level
for (int i = 0; i < size; i++) {
// Get the front node from the queue
TreeNode* node = nodesQueue.front();
nodesQueue.pop();
// Determine the index to insert the node's value based on the traversal direction
int index = leftToRight ? i : (size - 1 - i);
// Insert the node's value at the determined index
row[index] = node->data;
// Enqueue the left and right children if they exist
if (node->left) {
nodesQueue.push(node->left);
}
if (node->right) {
nodesQueue.push(node->right);
}
}
// Switch the traversal direction for the next level
leftToRight = !leftToRight;
// Add the current level's values to the result vector
result.push_back(row);
}
// Return the final result of zigzag level order traversal
return result;
}
};
// Helper function to print the result
void printResult(const vector<vector<int>>& result) {
for (const auto& row : result) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
}
int main() {
// Creating a sample binary tree
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
Solution solution;
// Get the zigzag level order traversal
vector<vector<int>> result = solution.zigzagLevelOrder(root);
// Print the result
printResult(result);
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596
import java.util.*;
class TreeNode {
int data;
TreeNode left, right;
TreeNode(int val) { data = val; left = null; right = null; }
}
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
// List to store the result of zigzag traversal
List<List<Integer>> result = new ArrayList<>();
// Check if the root is NULL, return an empty result
if (root == null) {
return result;
}
// Queue to perform level order traversal
Queue<TreeNode> nodesQueue = new LinkedList<>();
nodesQueue.add(root);
// Flag to determine the direction of traversal (left to right or right to left)
boolean leftToRight = true;
// Continue traversal until the queue is empty
while (!nodesQueue.isEmpty()) {
// Get the number of nodes at the current level
int size = nodesQueue.size();
// List to store the values of nodes at the current level
List<Integer> row = new ArrayList<>(Collections.nCopies(size, 0));
// Traverse nodes at the current level
for (int i = 0; i < size; i++) {
// Get the front node from the queue
TreeNode node = nodesQueue.poll();
// Determine the index to insert the node's value based on the traversal direction
int index = leftToRight ? i : (size - 1 - i);
// Insert the node's value at the determined index
row.set(index, node.data);
// Enqueue the left and right children if they exist
if (node.left != null) {
nodesQueue.add(node.left);
}
if (node.right != null) {
nodesQueue.add(node.right);
}
}
// Switch the traversal direction for the next level
leftToRight = !leftToRight;
// Add the current level's values to the result list
result.add(row);
}
// Return the final result of zigzag level order traversal
return result;
}
}
// Helper function to print the result
class Main {
public static void printResult(List<List<Integer>> result) {
for (List<Integer> row : result) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
// Creating a sample binary tree
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
Solution solution = new Solution();
// Get the zigzag level order traversal
List<List<Integer>> result = solution.zigzagLevelOrder(root);
// Print the result
printResult(result);
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
from collections import deque
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def zigzagLevelOrder(self, root):
# List to store the result of zigzag traversal
result = []
# Check if the root is NULL, return an empty result
if not root:
return result
# Queue to perform level order traversal
nodesQueue = deque([root])
# Flag to determine the direction of traversal (left to right or right to left)
leftToRight = True
# Continue traversal until the queue is empty
while nodesQueue:
# Get the number of nodes at the current level
size = len(nodesQueue)
# List to store the values of nodes at the current level
row = [0] * size
# Traverse nodes at the current level
for i in range(size):
# Get the front node from the queue
node = nodesQueue.popleft()
# Determine the index to insert the node's value based on the traversal direction
index = i if leftToRight else (size - 1 - i)
# Insert the node's value at the determined index
row[index] = node.val
# Enqueue the left and right children if they exist
if node.left:
nodesQueue.append(node.left)
if node.right:
nodesQueue.append(node.right)
# Switch the traversal direction for the next level
leftToRight = not leftToRight
# Add the current level's values to the result list
result.append(row)
# Return the final result of zigzag level order traversal
return result
# Helper function to print the result
def printResult(result):
for row in result:
print(" ".join(map(str, row)))
if __name__ == "__main__":
# Creating a sample binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
solution = Solution()
# Get the zigzag level order traversal
result = solution.zigzagLevelOrder(root)
# Print the result
printResult(result)
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null){
* this.data = val;
* this.left = left;
* this.right = right;
* }
* }
**/
class Solution {
zigzagLevelOrder(root) {
// Array to store the result of zigzag traversal
let result = [];
// Check if the root is NULL, return an empty result
if (!root) {
return result;
}
// Queue to perform level order traversal
let nodesQueue = [];
nodesQueue.push(root);
// Flag to determine the direction of traversal (left to right or right to left)
let leftToRight = true;
// Continue traversal until the queue is empty
while (nodesQueue.length) {
// Get the number of nodes at the current level
let size = nodesQueue.length;
// Array to store the values of nodes at the current level
let row = new Array(size);
// Traverse nodes at the current level
for (let i = 0; i < size; i++) {
// Get the front node from the queue
let node = nodesQueue.shift();
// Determine the index to insert the node's value based on the traversal direction
let index = leftToRight ? i : (size - 1 - i);
// Insert the node's value at the determined index
row[index] = node.data;
// Enqueue the left and right children if they exist
if (node.left) {
nodesQueue.push(node.left);
}
if (node.right) {
nodesQueue.push(node.right);
}
}
// Switch the traversal direction for the next level
leftToRight = !leftToRight;
// Add the current level's values to the result array
result.push(row);
}
// Return the final result of zigzag level order traversal
return result;
}
}
// Helper function to print the result
function printResult(result) {
result.forEach(row => {
console.log(row.join(' '));
});
}
// Creating a sample binary tree
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
let solution = new Solution();
// Get the zigzag level order traversal
let result = solution.zigzagLevelOrder(root);
// Print the result
printResult(result);
