Binary Tree Zigzag Level Order Traversal
Problem Statement :
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between). Example 1: Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]] Example 2: Input: root = [1] Output: [[1]] Example 3: Input: root = [] Output: []
Solution :
Solution in C :
int depth(struct TreeNode* root){
if(root == NULL)
return 0;
else
return 1 + fmax( depth(root->left), depth(root->right) );
}
int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
int dep = depth(root);
if(dep == 0){
*returnSize = 0;
return NULL;
}
*returnColumnSizes = malloc(dep * sizeof(int));
int** ans = malloc(dep * sizeof(int*));
int ans_idx = 0;
struct TreeNode** queue0 = malloc(1000 * sizeof(struct TreeNode* ));
struct TreeNode** queue1 = malloc(1000 * sizeof(struct TreeNode* ));
int idx0 = 0, idx1 = 0;
queue0[idx0] = root;
idx0 = 1;
while(idx0 || idx1){
if(idx0){
ans[ans_idx] = malloc(idx0 * sizeof(int));
returnColumnSizes[0][ans_idx] = idx0;
for(int i = idx0-1; i >=0; i--){
ans[ans_idx][idx0-1-i] = queue0[i]->val;
if(queue0[i]->left){
queue1[idx1] = queue0[i]->left;
idx1++;
}
if(queue0[i]->right){
queue1[idx1] = queue0[i]->right;
idx1++;
}
}
ans_idx++;
idx0 = 0;
}
else{
ans[ans_idx] = malloc(idx1 * sizeof(int));
returnColumnSizes[0][ans_idx] = idx1;
for(int i = idx1-1; i >=0; i--){
ans[ans_idx][idx1-1-i] = queue1[i]->val;
if(queue1[i]->right){
queue0[idx0] = queue1[i]->right;
idx0++;
}
if(queue1[i]->left){
queue0[idx0] = queue1[i]->left;
idx0++;
}
}
ans_idx++;
idx1 = 0;
}
}
*returnSize = dep;
return ans;
}
Solution in C++ :
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
queue<TreeNode*> q;
q.push(root);
bool flag = true;
while(!q.empty()) {
int size = q.size();
vector<int> row(size);
for(int i = 0; i<size; i++) {
TreeNode* node = q.front();
q.pop();
int ind = (flag) ? i:(size-1-i);
row[ind] = node->val;
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
flag = !flag;
res.push_back(row);
}
return res;
}
};
Solution in Java :
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
boolean flag = true;
while (!q.isEmpty()) {
int size = q.size();
List<Integer> row = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
int index = flag ? i : (size - 1 - i);
row.add(index, node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
res.add(row);
flag = !flag;
}
return res;
}
}
Solution in Python :
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res = []
q = deque([root])
flag = True
while q:
size = len(q)
row = [0] * size
for i in range(size):
node = q.popleft()
index = i if flag else size - 1 - i
row[index] = node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(row)
flag = not flag
return res
View More Similar Problems
Minimum Average Waiting Time
Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h
View Solution →Merging Communities
People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w
View Solution →Components in a graph
There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu
View Solution →Kundu and Tree
Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that
View Solution →Super Maximum Cost Queries
Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and
View Solution →Contacts
We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co
View Solution →