Using 2 stack , easy implementation


  • 0
    N

    idea is simple , you use two stack for level odd and level even respectively , and proceed with adding nodes for level i+1 in level i until your stack of level i is empty . Code will help you understand more .

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> vv;
            if(root==NULL)
            return vv;
            
            stack<TreeNode*> s1;
            stack<TreeNode*> s2;
            
            
            s1.push(root);
            
            while(!s1.empty() || !s2.empty())
            {
                vector<int> v;
                while(!s1.empty())
                {
                    TreeNode* temp=s1.top();
                    s1.pop();
                    if(temp)
                    v.push_back(temp->val);
                    
                    if(temp->left)
                    s2.push(temp->left);
                    
                    if(temp->right)
                    s2.push(temp->right);
                    
                    if(s1.empty())
                    {
                          vv.push_back(v);
                          v.clear();
                    }
                    
                }
                
             
                
                while(!s2.empty())
                {
                    TreeNode* temp=s2.top();
                    s2.pop();
                    if(temp)
                    v.push_back(temp->val);
                    
                    if(temp->right)
                    s1.push(temp->right);
                    
                    if(temp->left)
                    s1.push(temp->left);
                    
                    if(s2.empty())
                    {
                          vv.push_back(v);
                          v.clear();
                    }
                
                }
               
              
            }
            return vv;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.