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;
        Queue<TreeNode> q = new LinkedList<>();
        boolean reverse=false;
        q.offer(root);
        while(!q.isEmpty()){
            int l = q.size(); 
            List<Integer> ll = new LinkedList<>();

            for(int i=0; i < l ; i++){
                
                TreeNode ln = q.poll();
                if(reverse) ll.add(0,ln.val);
                else ll.add(ln.val);
                if(ln.left!=null) q.offer(ln.left);
                if(ln.right!=null) q.offer(ln.right);
            
            }
            res.add(ll);
            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;
}