My Simple C++ 4ms solution with two stacks[With Explanation]


  • 0
    Y

    I use two stacks to switch around of reading them in a same way of BFS. very easy

    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            stack<TreeNode*> s1;
            stack<TreeNode*> s2;
            
            vector<vector<int>> result;
            
            if (!root) s1.push(root);
            while(!s1.empty() || !s2.empty()){
                int size = result.size();
                vector<int> vec;
                if (size % 2 == 0){
                    while(!s1.empty()){
                        TreeNode* p = s1.top();
                        s1.pop();
                        vec.push_back(p->val);
                        if (p->left) s2.push(p->left);
                        if (p->right) s2.push(p->right);
                    }
                }
                else {
                    while(!s2.empty()){
                        TreeNode* p = s2.top();
                        s2.pop();
                        vec.push_back(p->val);
                        if (p->right) s1.push(p->right);
                        if (p->left) s1.push(p->left);
                    }
                }
                result.push_back(vec);
            }
            
            return result;
        }
    };

Log in to reply
 

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