c++ 4ms using queue


  • 0
    X
    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> ans;
            if(root == NULL){
                return ans;
            }
            queue<TreeNode*> q;
            TreeNode flag(-1);
            q.push(root);
            q.push(&flag);
            int d = 1;
            vector<int> tmp;
            while(!q.empty()){
                TreeNode* t = q.front();
                q.pop();
                if(t == &flag){
                    ans.push_back(tmp);
                    tmp.clear();
                    d = -d;
                    if(q.empty()){
                        break;
                    }else{
                        q.push(&flag);
                    }
                }else{
                    if(d == 1){
                        tmp.insert(tmp.end(), t->val);
                    }else{
                        tmp.insert(tmp.begin(), t->val);
                    }
                    
                    if(t->left != NULL){
                        q.push(t->left);
                    }
                    if(t->right != NULL){
                        q.push(t->right);
                    }
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

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