c++ solution using two stack, 3ms


  • 0
    M

    Two stacks are alternated as the container of the nodes. How about that? ; P

    Notice the left - right and right - left order for two different stacks.

    class Solution {
    public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        stack<TreeNode*> s, s1;
        vector<vector<int>> res;
        TreeNode* node;
        
        if (root==NULL) return res;
        s.push(root);
        while (!s.empty()){
            res.push_back(vector<int> ());
            while (!s.empty()){
                node = s.top();
                s.pop();
                res.back().push_back(node->val);
                if (node->left) s1.push(node->left);
                if (node->right) s1.push(node->right);
            }
            if (s1.empty()) break;
            res.push_back(vector<int> ());
            while (!s1.empty()){
                node = s1.top();
                s1.pop();
                res.back().push_back(node->val);
                if (node->right) s.push(node->right);
                if (node->left) s.push(node->left);
            }
        }
        return res;   
    }
    };

Log in to reply
 

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