A intuitive idea implementation with two stack


  • 0
    Z

    class Solution {
    public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> res;
    stack<TreeNode*> s1;
    stack<TreeNode*> s2;
    if(root==NULL) return res;

        s1.push(root);
        while(!s1.empty() || !s2.empty() ){
            res.push_back(vector<int>{});
            while(!s1.empty()){
                //right to left
                TreeNode* top = s1.top();
                res.back().push_back(top->val);
                s1.pop();
                if(top->left) s2.push(top->left);
                if(top->right) s2.push(top->right);
            }
            if(!s2.empty())res.push_back(vector<int>{});
            while(!s2.empty()){
                TreeNode* top = s2.top();
                res.back().push_back(top->val);
                s2.pop();
                if(top->right) s1.push(top->right);
                if(top->left) s1.push(top->left);
            }
        }
        
        return res;
    }
    

    };


Log in to reply
 

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