using deque to implement Zigzag level traversal


  • 0
    L

    we can draw conclusion that current level from left to right, the next level should be from right to left, so
    a deque of C++ STL can be used.

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            deque<TreeNode*> dque;
            vector<vector<int>> res;
            vector<int> vlevel;
            if(!root)
                return res;
            dque.push_back(root);
            int level1=1,level2=0;
            int front=0;//from left to right or right to left
            TreeNode* proot;
            while(!dque.empty()){
                if(front){
                    proot =  dque.front();
                    dque.pop_front();               
                }else{
                    proot = dque.back();
                    dque.pop_back();
                }
                
                vlevel.push_back(proot->val);
                if(front){//push back to queue
                    if(proot->right){
                        dque.push_back(proot->right);
                        ++level2;
                    }
                    
                    if(proot->left){
                        dque.push_back(proot->left);
                        ++level2;
                    }
                    
                }else{//push front to deque
                    
                    if(proot->left){
                        dque.push_front(proot->left);
                        ++level2;
                    }
                    
                    if(proot->right){
                        dque.push_front(proot->right);
                        ++level2;
                    }
                }
                if(--level1 == 0){//one level is over...
                    front = 1- front;
                    res.push_back(vlevel);
                    level1 = level2;
                    level2 = 0;
                    // swap(level1,level2);
                    vlevel.clear();
                }
            }
            return res;
        }
    

Log in to reply
 

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