C++_6ms_Using two stacks_Accepted_Easy to Understand


  • 0

    #I think my method can be improved by using queue
    #however, by using queue, we should know the beginning and end node for each level.

    #code block

        class Solution {
        public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == NULL) return res;
        stack<TreeNode*> s1;
        stack<TreeNode*> s2;
        s1.push(root);
        int indt = 1;//1:from left to right, 2: from right to left;
        while(true){
            vector<int> path;
            if(indt == 1){
                while(!s1.empty()){
                    TreeNode* node = s1.top();
                    s1.pop();
                    path.push_back(node->val);
                    if(node->left){s2.push(node->left);}
                    if(node->right){s2.push(node->right);}
                }
                res.push_back(path);
                if(s2.empty()) break;
                indt = 2;
            }
            else if(indt == 2){
                while(!s2.empty()){
                    TreeNode* node = s2.top();
                    s2.pop();
                    path.push_back(node->val);
                    if(node->right){s1.push(node->right);}
                    if(node->left){s1.push(node->left);}
                }
                res.push_back(path);
                if(s1.empty()) break;
                indt = 1;
            }
        }
        return res;}    };

Log in to reply
 

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