[C++] [3ms] Using two stacks, iterative.


  • 0
    M

    I have tried to use two stacks for this problem. Each stack will be used alternatively for storing the next level of nodes to be processed.
    Two stack are needed, as at a time I am reading from one stack and then pushing the next level nodes into another stack.
    Order of pushing the next level nodes is more important. When I am processing any odd level node then I push the 'left' child before 'right' child of currently processed node. In case of even level node, I push right child before left child in stack.

    '''

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(!root) return result;
        
        stack<TreeNode*> s1;
        stack<TreeNode*> s2;
        
        s1.push(root);
        int level = 1;
        while(!s1.empty() || !s2.empty()) 
        {
            bool bLeftToRight = (level % 2 == 1);
            stack<TreeNode*>& toProcess =  bLeftToRight ? s1 : s2;
            stack<TreeNode*>& toSave = bLeftToRight ? s2 : s1;
            
            vector<int> row(toProcess.size());
            int idx = 0;
            while(!toProcess.empty())
            {
                TreeNode* node = toProcess.top();
                toProcess.pop();
                row[idx++] = node->val;
                
                TreeNode* firstNode = bLeftToRight ? node->left : node->right;
                TreeNode* secondNode = !bLeftToRight ? node->left : node->right;
                if(firstNode)
                    toSave.push(firstNode);
                if(secondNode)
                    toSave.push(secondNode);
            }
            result.push_back(row);
            
            ++level;
        }
        
        return result;
    }
    

    '''


Log in to reply
 

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