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 :



title-img


                            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 →