Binary Tree Zigzag Level Order Traversal

 Binary Tree Zigzag Level Order Traversal

 // /**

//  * 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)return {};

//         queue<TreeNode*> q;

//         q.push(root);

//         vector<vector<int> > ans;

//         vector<int> res;

//         int i=0;

//         while(!q.empty())

//         {

//             int s=q.size();

//             res.clear();

//             while(s--)

//             {

//                auto p=q.front();

//                 q.pop();

//                 res.push_back(p->val);

//                 if(p->left)

//                     q.push(p->left);

//                 if(p->right)

//                     q.push(p->right);

//             }

//             if(i){

//             reverse(res.begin(),res.end());

//             }

//             ans.push_back(res);

//             i=!i;

//         }

//         return ans;

        

//     }

// };

class Solution 

{

public:

    vector<vector<int>> ans;

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

        

        if (!root) return ans;

        

        stack<TreeNode*> s1;

        stack<TreeNode*> s2;

        

        s1.push(root);

        while(s1.size() || s2.size()) {

            vector<int> v;

            while (s1.size()) {

                TreeNode *node = s1.top();

                v.push_back(node->val);

                s1.pop();

                if (node->left)

                    s2.push(node->left);

                if (node->right)

                    s2.push(node->right); 

            }

            if (v.size())

                ans.push_back(v);

            v.clear();

            while (s2.size()) 

            {

                TreeNode *node = s2.top();

                v.push_back(node->val);

                s2.pop();

                if (node->right)

                    s1.push(node->right);

                if (node->left)

                    s1.push(node->left);  

             }

            

            if (v.size())

                ans.push_back(v);

            v.clear();

        }

        return ans;

    }

};