1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10  * };
11  */
12 class Solution {
13 public:
14     vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
15     {
16         stack<TreeNode*> st;
17         vector<vector<int>> res;
18         if(!root)
19         return res;
20         st.push(root);
21         bool LeftorRight = true;
22         while(!st.empty())
23         {
24             if(LeftorRight)
25             {
26                 vector<int> res_temp;
27                 stack<TreeNode*> st_temp;
28                 TreeNode* temp;
29                 while(!st.empty())
30                 {
31                     temp = st.top();
32                     st.pop();
33                     res_temp.push_back(temp->val);
34                     if(temp->left)
35                     st_temp.push(temp->left);
36                     if(temp->right)
37                     st_temp.push(temp->right);
38                 }
39                 res.push_back(res_temp);
40                 st = st_temp;
41                 LeftorRight = !LeftorRight;
42             }
43             else
44             {
45                 vector<int> res_temp;
46                 stack<TreeNode*> st_temp;
47                 TreeNode* temp;
48                 while(!st.empty())
49                 {
50                     temp = st.top();
51                     st.pop();
52                     res_temp.push_back(temp->val);
53                     if(temp->right)
54                     st_temp.push(temp->right);
55                     if(temp->left)
56                     st_temp.push(temp->left);
57                 }
58                 res.push_back(res_temp);
59                 st = st_temp;
60                 LeftorRight = !LeftorRight;
61             }
62         }
63         return res;
64     }
65 };

/**
 * 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) 
    {
        vector<vector<int>> res;
        if(!root)
        return res;
        bool LeftorRight = true;
        queue<TreeNode*> nodeQueue;
        nodeQueue.push(root);
        while(!nodeQueue.empty())
        {
            deque<int> res_temp;
            int size = nodeQueue.size();
            for(int i = 0 ; i < size ; i++)
            {
                TreeNode* Node = nodeQueue.front();
                nodeQueue.pop();
                if(LeftorRight)
                {
                    res_temp.push_back(Node->val);
                }
                else
                {
                    res_temp.push_front(Node->val);
                }
                if(Node->left)
                nodeQueue.push(Node->left);
                if(Node->right)
                nodeQueue.push(Node->right);
            }
            res.emplace_back(vector<int>{res_temp.begin(),res_temp.end()});
            LeftorRight = !LeftorRight;
        }
        return res;
        
    }
};