Sponsored
Sponsored
This approach leverages the standard Breadth-First Search (BFS) algorithm to perform a level order traversal. We use a queue to traverse the tree level-by-level. For each level, we determine the order (left-to-right or right-to-left) by toggling a flag. At odd levels, we simply reverse the order of elements collected from the queue to achieve the zigzag effect.
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is processed once.
Space Complexity: O(n), for storing the output and additional structures, like the queue used for BFS.
1#include <stdio.h>
2#include <stdlib.h>
3
4// Definition for a binary tree node.
5typedef struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9} TreeNode;
10
11void reverse(int* arr, int left, int right) {
12 while (left < right) {
13 int temp = arr[left];
14 arr[left++] = arr[right];
15 arr[right--] = temp;
16 }
17}
18
19int** zigzagLevelOrder(TreeNode* root, int** columnSizes, int* returnSize) {
20 if (!root) {
21 *returnSize = 0;
22 return NULL;
23 }
24
25 int** result = (int**) malloc(2000 * sizeof(int*));
26 int* sizes = (int*) malloc(2000 * sizeof(int));
27 *returnSize = 0;
28
29 TreeNode** queue = (TreeNode**) malloc(2000 * sizeof(TreeNode*));
30 int front = 0, rear = 0;
31 queue[rear++] = root;
32
33 int level = 0;
34 while (front < rear) {
35 int count = rear - front;
36 int* levelVals = (int*) malloc(count * sizeof(int));
37 for (int i = 0; i < count; ++i) {
38 TreeNode* node = queue[front++];
39 levelVals[i] = node->val;
40 if (node->left) queue[rear++] = node->left;
41 if (node->right) queue[rear++] = node->right;
42 }
43
44 if (level % 2 == 1) {
45 reverse(levelVals, 0, count - 1);
46 }
47
48 result[*returnSize] = levelVals;
49 sizes[*returnSize] = count;
50 (*returnSize)++;
51 level++;
52 }
53
54 *columnSizes = sizes;
55 free(queue);
56 return result;
57}This C solution uses a queue to perform a level order traversal of the tree. It maintains an array of lists, where each list contains values of nodes at the same level. We also keep track of the direction using the level number: odd levels are reversed using an auxiliary reverse function. This solution balances both clarity and efficiency.
In contrast to the BFS method, this approach utilizes Depth-First Search (DFS) for traversal. Recursive calls are made to process each node, and a hashmap (or similar structure) tracks the current depth. Depending on the depth, nodes are appended to the left or right of the current level list. This achieves the zigzag pattern as the recursion progresses.
Time Complexity: O(n), as DFS visits each node once.
Space Complexity: O(n), considering both storage needs for recursive calls and the result list.
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
dfs(root, 0, res);
return res;
}
private:
void dfs(TreeNode* node, int depth, vector<vector<int>>& res) {
if (node == NULL) return;
if (depth >= res.size()) {
res.push_back(vector<int>());
}
if (depth % 2 == 0) {
res[depth].push_back(node->val);
} else {
res[depth].insert(res[depth].begin(), node->val);
}
dfs(node->left, depth + 1, res);
dfs(node->right, depth + 1, res);
}
};Using C++, this solution leverages DFS with depth-based bookkeeping to form the zigzag pattern. Collections for each level are managed with insertions according to depth, and recursion handles tree traversal seamlessly.