Two stack algorithm


  • 0
    N

    Use two stacks, pushing the nodes of the tree in difference sequence to the stack. For the level visiting from left to right, we push its sub tree by the left--right child order. For the right to left, we push its child by right-left order.

       vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> result;
            if(!root)
                return result;
            stack<TreeNode*> S;
            S.push(root);
            stack<TreeNode*> T;
            vector<int> level;
            TreeNode* temp = NULL;
    
            while(!S.empty() || !T.empty()){
                while(!S.empty()){
                    temp = S.top();
                    S.pop();
                    level.push_back(temp->val);
                    if(temp->left){
                        T.push(temp->left);
                    }
                    if(temp->right){
                        T.push(temp->right);
                    }
                }
                if(level.size()){//one level is done
                    result.push_back(level);
                    level.clear();
                }
                
                while(!T.empty()){
                    temp = T.top();
                    T.pop();
                    level.push_back(temp->val);
                    if(temp->right){
                        S.push(temp->right);
                    }
                    if(temp->left){
                        S.push(temp->left);
                    }
                }
                if(level.size()){
                    result.push_back(level);
                    level.clear();
                }
            }
            //return the result;
            return result;
        }

Log in to reply
 

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