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; }