LC 103. Binary Tree Zigzag Level Order Traversal

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (root == NULL) return {};
        vector<vector<int>> ans;
        int mode = 1;
        vector<TreeNode*> st;
        st.push_back(root);
        while (st.size()) {
            int sz = st.size();
            vector<TreeNode*> nst;
            vector<int> tmp;
            while (sz--) {
                TreeNode *cur = st.back();
                st.pop_back();
                tmp.push_back(cur -> val);
                if (mode == 1) {
                    if (cur -> left) nst.push_back(cur -> left);
                    if (cur -> right) nst.push_back(cur -> right);
                } else {
                    if (cur -> right) nst.push_back(cur -> right);
                    if (cur -> left) nst.push_back(cur -> left);
                }
            }
            ans.push_back(tmp);
            st = nst;
            mode *= -1;
        }
        return ans;
    }
};

Time Complexity: O(n)
Space: O(n)