C++ solution with two stacks;


  • 0
    Z

    I use stk0 to store the level 0,

    and then pop the stk0 meanwhile store the level 1 in the stk1.

    and then pop the stk1 meanwhile store the level 2 in the stk0.

    and .....

    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int>> res;
        if(!root)return res;
        
        int level=0;
        vector<int> tmp;
        TreeNode *curr=NULL;
        vector<TreeNode*> stk0,stk1;//preparation.
        
        stk0.push_back(root);//store level 0
        
        while(stk0.size()){
            res.push_back(tmp);
            while(stk0.size()){
                curr=stk0.back();
                stk0.pop_back();//pop stk0 
                if(curr->left)stk1.push_back(curr->left);//store the next level in the stk1;
                if(curr->right)stk1.push_back(curr->right);
                res[level].push_back(curr->val);
            }
            level++;
            
            if(!stk1.size())break;
            res.push_back(tmp);
            
            while(stk1.size()){
                curr=stk1.back();
                stk1.pop_back();//pop stk1
                if(curr->right)stk0.push_back(curr->right);//store the next level in the stk0;
                if(curr->left)stk0.push_back(curr->left);
                res[level].push_back(curr->val);
            }
            level++;
        }
        return res;
    }

Log in to reply
 

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