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

Constraints:

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

Intuition

Links

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Video Links

Approach 1:

C++

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == NULL)
            return ans;

        queue<TreeNode*> q;
        q.push(root);
        bool flag = true;

        /*
        Basically just add the left and right to queue 
        just like Level order traversal

        Then based on flag just input in reverse or same order and go on
        */

        while (!q.empty()) {
            int size = q.size();
            vector<int> val(size);
            for(int i = 0; i < size; i++) {
                TreeNode *temp = q.front();
                q.pop();

                int index = (flag) ? i : (size-1-i);
                // Logic to input in reverse or same order

                val[index] = temp->val;
                if(temp->left != nullptr)   q.push(temp->left);
                if(temp->right != nullptr)   q.push(temp->right);
            }

            flag = !flag;
            //Change of flag after each iteration
            ans.push_back(val);
        }

        return ans;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++