103 - Binary Tree Zigzag Level Order Traversal

#medium

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

/**
 * 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>> result;
        queue<TreeNode*> que;
        que.push( root );
        bool isOdd = true;
        while ( !que.empty() ) {
            int que_size = que.size();
            vector<int> one_level = {};
            for ( int i = 0; i < que_size; i++ ) {
                TreeNode * node = que.front();
                que.pop();
                one_level.push_back( node -> val );
                if ( node -> left != NULL ) que.push( node -> left );
                if ( node -> right != NULL ) que.push( node -> right );

            }

            if ( isOdd ) {
                isOdd = false; 
                result.push_back( one_level );
            }
            else {
                isOdd = true;
                reverse( one_level.begin(), one_level.end() );
                result.push_back( one_level );
            }

        }

        return result;
    }
};