Iterative BFS cpp solution using two stacks


  • 0
    C
    class Solution {
    public:
        
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
        {
            vector< vector<int> >  result;
            
            if(!root) return result;
            
            stack<TreeNode*> s_l2r, s_r2l;
            s_l2r.push(root);
            
            while( !(s_l2r.empty() && s_r2l.empty()) )
            {
                result.push_back( vector<int>() );
                vector< vector<int> >::iterator vec_iter = result.end()-1;
                
                if( !s_l2r.empty() )
                {
                    while( !s_l2r.empty() )
                    {
                        TreeNode *node = s_l2r.top();
                        s_l2r.pop();
                        
                        vec_iter->push_back(node->val);
                        
                        if(node->left) s_r2l.push(node->left);
                        if(node->right) s_r2l.push(node->right);
                    }
                }
                else
                {
                    while( !s_r2l.empty() )
                    {
                        TreeNode *node = s_r2l.top();
                        s_r2l.pop();
                        
                        vec_iter->push_back(node->val);
                        
                        if(node->right) s_l2r.push(node->right);
                        if(node->left) s_l2r.push(node->left);
                    }
                }
            }
            
            return result;
        }
    };

Log in to reply
 

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