Leetcode - Binary Tree Zig Zag Level Order Traversal

link

Problem

Traverse the tree verticall from left to right

Solution

Level order traversal with two stacks. Second stack should store the children reversely (right and left)

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> list;
        if(root){
            stack<TreeNode*> s1;
            stack<TreeNode*> s2;
            s1.push(root);
            while(!s1.empty() || !s2.empty()){
                if(!s1.empty()){
                    list.resize(list.size() + 1);
                }
                while(!s1.empty()){
                    TreeNode* cur = s1.top();
                    s1.pop();
                    if(cur->left){
                        s2.push(cur->left);
                    }
                    if(cur->right){
                        s2.push(cur->right);
                    }
                    list[list.size()-1].push_back(cur->val);
                }
                if(!s2.empty()){
                    list.resize(list.size()+1);
                }
                while(!s2.empty()){
                    TreeNode* cur = s2.top();
                    s2.pop();
                    if(cur->right){
                        s1.push(cur->right);
                    }
                    if(cur->left){
                        s1.push(cur->left);
                    }
                    list[list.size()-1].push_back(cur->val);
                }
            }
        }
        
        return list;
    }

Time Complexity : O(n)