C++ 4ms 2 stacks with comments


  • 0
    J
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> ret;
            if(root == NULL)
                return ret;
            std::stack<TreeNode *> stk, temp;
            stk.push(root);
            bool zigzag = true; // zigzag flag
            while(!stk.empty())
            {
                vector<int> rec;
                temp = stk; // copy current stack
                while(!stk.empty())
                {// record this level's values
                    TreeNode * n = stk.top();
                    rec.push_back(n->val);
                    stk.pop();
                }
                // add to return vector
                ret.push_back(rec);
                // add next level in zigzag mode
                while(!temp.empty())
                {
                    TreeNode * n = temp.top();
                    if(zigzag)
                    {// right->left
                        if(n->left)
                            stk.push(n->left);
                        if(n->right)
                            stk.push(n->right);
                    }
                    else
                    {// left->right
                        if(n->right)
                            stk.push(n->right);
                        if(n->left)
                            stk.push(n->left);
                    }
                    
                    temp.pop();
                }
                zigzag = !zigzag;
            }
            return ret;
        }

Log in to reply
 

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