In this post, we are going to solve the 103. Binary Tree Zigzag Level Order Traversal problem of Leetcode. This problem 103. Binary Tree Zigzag Level Order Traversal is a Leetcode medium level problem. Let’s see the code, 103. Binary Tree Zigzag Level Order Traversal – Leetcode Solution.

Problem

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: []

Constraints

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Now, let’s see the code of 103. Binary Tree Zigzag Level Order Traversal – Leetcode Solution.

Binary Tree Zigzag Level Order Traversal – Leetcode Solution

103. Binary Tree Zigzag Level Order Traversal – Solution in Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        
        List<List<Integer>> outer = new ArrayList<List<Integer>>();
        if(root == null) return outer;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        
        q.add(root);
        boolean flag = false;
        
        while(!q.isEmpty()){
            List<Integer> inner = new ArrayList<Integer>();
            int size = q.size();
            
            while(size-- > 0){
                TreeNode node = q.poll();
                inner.add(node.val);
                if(node.left != null)q.add(node.left);
                if(node.right != null)q.add(node.right);
            }
             
            if(flag == false){
                outer.add(inner);
                flag = true;
            }else if(flag == true){
                Collections.reverse(inner);
                outer.add(inner);
                flag = false;
            }
            
        }
        return outer;
    }
}

103. Binary Tree Zigzag Level Order Traversal – Solution in C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        if (root == NULL) {
            return vector<vector<int> > ();
        }
        vector<vector<int> > result;

        queue<TreeNode*> nodesQueue;
        nodesQueue.push(root);
        bool leftToRight = true;

        while ( !nodesQueue.empty()) {
            int size = nodesQueue.size();
            vector<int> row(size);
            for (int i = 0; i < size; i++) {
                TreeNode* node = nodesQueue.front();
                nodesQueue.pop();

                int index = (leftToRight) ? i : (size - 1 - i);

                row[index] = node->val;
                if (node->left) {
                    nodesQueue.push(node->left);
                }
                if (node->right) {
                    nodesQueue.push(node->right);
                }
            }

            leftToRight = !leftToRight;
            result.push_back(row);
        }
        return result;
    }
};

103. Binary Tree Zigzag Level Order Traversal – Solution in Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []
        res, temp, stack, flag=[], [], [root], 1
        while stack:
            for i in xrange(len(stack)):
                node=stack.pop(0)
                temp+=[node.val]
                if node.left: stack+=[node.left]
                if node.right: stack+=[node.right]
            res+=[temp[::flag]]
            temp=[]
            flag*=-1
        return res
        

Note: This problem 103. Binary Tree Zigzag Level Order Traversal is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.