C++ solution using 2 stacks without reverse operation


  • 0
    K
    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            if(root==NULL) return {};
            vector<vector<int>>res;
            stack<TreeNode*> stk1,stk2;
            stk1.push(root);
            while(!stk1.empty()||!stk2.empty())
            {
                vector<int> tempVal;
                if(!stk1.empty())
                    while(!stk1.empty())
                    {
                        TreeNode *node=stk1.top();
                        if(node->left) stk2.push(node->left);
                        if(node->right) stk2.push(node->right);
                        tempVal.push_back(node->val);
                        stk1.pop();
                    }
                else
                    while(!stk2.empty())
                    {
                        TreeNode *node=stk2.top();
                        if(node->right) stk1.push(node->right);
                        if(node->left) stk1.push(node->left);
                        tempVal.push_back(node->val);
                        stk2.pop();
                    }
                res.push_back(tempVal);
            }
            return res;
        }
    };

Log in to reply
 

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