4ms C++ deque Solution - Long but Different, Feedback?


  • 0
    S
    class Solution {
    private: 
    vector    <vector<int>> vec;
    public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(!root) return vec;
        
        int count_odd = 1;
        int count_even = 0;
        deque<TreeNode *> abc;
        abc.push_front(root);
        bool odd = true;
        int level = 0;
        vec.push_back(vector<int>());
    
        while(!abc.empty()) {
            //In odd levels,push_front pop_back, left first, right next, keep count on how many nodes are being pushed, how many nodes to pop
            //In Even levels, push_back,pop_front, right first, left next, keep count on how many nodes are being pushed, how many nodes to pop 
                if(odd) {
                    auto node = abc.back();
                    vec[level].push_back(node->val);
                    abc.pop_back();
                    if(node->left) {
                        abc.push_front(node->left);
                        count_even++;
                    }
                    if(node->right) {
                        abc.push_front(node->right);
                        count_even++;
                        
                    }
                    if(--count_odd == 0) {
                        odd = false;
                        level++;
                        vec.push_back(vector<int>());
                    }
                } else {
                    
                    auto node = abc.front();
                    vec[level].push_back(node->val);
    
                    abc.pop_front();
                    if(node->right) {
                        abc.push_back(node->right);
                        count_odd++;
                    }
                    if(node->left) {
                        abc.push_back(node->left);
                        count_odd++;
                    }
                    if(--count_even == 0) {
                        odd = true;
                        level++;
                        vec.push_back(vector<int>());   
                    }
    
                }
    
        }
        vec.pop_back();
    
        return vec;
        
    }
    

    };


Log in to reply
 

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