4ms C++ Solution with double stacks


  • 0
    F
    class Solution 
    {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
        {
            if(root == NULL)
            {
                return vector<vector<int>>(0);
            }
            
            vector<vector<int>> solution;
            stack<TreeNode*> evenStack;
            stack<TreeNode*> oddStack;
            
            evenStack.push(root);
            
            while(!evenStack.empty() || !oddStack.empty())
            {
                solution.push_back(vector<int>(0));
                int index = solution.size()-1;
                if(!evenStack.empty())
                {
                    getNextLayer(evenStack, oddStack, true, solution[ index ]);
                }
                else
                {
                    getNextLayer(oddStack, evenStack, false, solution[ index ]);
                }
            }
            
            return solution;
        }
        
    private:
        void getNextLayer(stack<TreeNode*>& poppedStack, stack<TreeNode*>& targetStack, bool isEvenLayer, vector<int>& solution)
        {
            while(!poppedStack.empty())
            {
                TreeNode* curNode = poppedStack.top();
                poppedStack.pop();
                if(isEvenLayer)
                {
                    if(curNode->left != NULL)
                    {
                        targetStack.push(curNode->left);
                    }
                    if(curNode->right != NULL)
                    {
                        targetStack.push(curNode->right);
                    }
                }
                else
                {
                    if(curNode->right != NULL)
                    {
                        targetStack.push(curNode->right);
                    }
                    if(curNode->left != NULL)
                    {
                        targetStack.push(curNode->left);
                    }
                }
                solution.push_back(curNode->val);
            }
        }
    };

Log in to reply
 

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