# Leetcode Binary Tree Zigzag Level Order Traversal problem solution

In this Leetcode Binary Tree Zigzag Level Order Traversal problem solution we have Given the root of a binary tree, return the zigzag level order traversal of its nodes' values.

## Problem solution in Python.

```class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:

to_right = 1

if root == None:
return []

cur_queue = [root]
next_queue = []
result = []
tmp = []
while(cur_queue):

node = cur_queue.pop()
tmp.append(node.val)
if(to_right):
if(node.left):
next_queue.append(node.left)
if(node.right):
next_queue.append(node.right)
else:
if(node.right):
next_queue.append(node.right)
if(node.left):
next_queue.append(node.left)

if(not cur_queue):
cur_queue = next_queue
next_queue = []
to_right = not to_right
result.append(tmp)
tmp = []

return result
```

## Problem solution in Java.

```public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root==null) return res;
boolean reverse=false;
q.offer(root);
while(!q.isEmpty()){
int l = q.size();

for(int i=0; i < l ; i++){

TreeNode ln = q.poll();
if(ln.left!=null) q.offer(ln.left);
if(ln.right!=null) q.offer(ln.right);

}
reverse = reverse?false:true;
}
return res;

}
```

## Problem solution in C++.

```vector<vector<int>> ans;
class Solution {
public:
void helper(TreeNode* root,int level=0)
{
if(root==NULL)
return;
if(level>=ans.size())
{
ans.resize(level+1);
}
if(level&1)
{
ans[level].insert(ans[level].begin()+0,root->val);
}
else{
ans[level].push_back(root->val);
}
helper(root->left,level+1);
helper(root->right,level+1);
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
ans.clear();
ans.resize(0);
helper(root);
return ans;
}
};
```

## Problem solution in C.

```#include<math.h>
int max (int a, int b)
{
return (a>b?a:b);
}

int findHieght(struct TreeNode *root)
{
if(root == NULL) return 0;
int lt = findHieght(root->left);
int rt = findHieght(root->right);
return 1 + max(lt,rt);
}

int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){

int **sol;
int ht = findHieght(root), currLevel;
struct TreeNode* s1[1024];
struct TreeNode* s2[1024];
struct TreeNode* tmp;
int top1, top2, col;
int i, j;

top1 = top2 = -1;
*returnSize = ht;
if (root == NULL) return NULL;

sol = (int **)malloc(sizeof(int *)*ht);
*returnColumnSizes = (int *)malloc (sizeof(int) * ht);
s1[++top1] = root;
currLevel = -1;
col = 0;
while (top1 != -1 || top2 != -1) {
if (top1 != -1) {
sol[++currLevel] = (int *)malloc(sizeof(int)*(top1+1));
col = 0;
}
while(top1 != -1) {
tmp = s1[top1--];
if (tmp->left) s2[++top2] = tmp->left;
if (tmp->right) s2[++top2] = tmp->right;
sol[currLevel][col++] = tmp->val;
(*returnColumnSizes)[currLevel] = col; /* 1 based indexing */

}

if (top2 != -1) {
sol[++currLevel] = (int *)malloc(sizeof(int)*(top2+1));
col = 0;
}
while(top2 != -1) {
tmp = s2[top2--];
if (tmp->right) s1[++top1] = tmp->right;
if (tmp->left) s1[++top1] = tmp->left;
sol[currLevel][col++] = tmp->val;
(*returnColumnSizes)[currLevel] = col;
}
}
*returnSize = ht;
#if 0
for (i=0;i<ht;i++) {
for (j=0;j<(*returnColumnSizes)[i]; j++) {
printf("%d ", sol[i][j]);
}
}
#endif
return sol;
}
```