c++ double stack BFS solution, by Chaoyang He


  • 1
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> result;
            if(root == NULL){
                return result;
            }
            stack<TreeNode*> stackZig;//left->right
            stack<TreeNode*> stackZag;//right->left
            
            TreeNode* node = root;
            stackZig.push(node);
            bool bForward = false;
            while(!stackZig.empty() || !stackZag.empty()){
                vector<int> levelResult;
                if(!bForward){
                    int levelNumZig = stackZig.size();
                    for(int i = 0; i < levelNumZig; i++){
                        //visit
                        node = stackZig.top();
                        stackZig.pop();
                        levelResult.push_back(node->val);
                        if(node->left != NULL){
                            stackZag.push(node->left);
                        }
                        if(node->right != NULL){
                            stackZag.push(node->right);
                        }
                    }
                }else{
                    int levelNumZag = stackZag.size();
                    for(int i = 0; i < levelNumZag; i++){
                        //visit
                        node = stackZag.top();
                        stackZag.pop();
                        levelResult.push_back(node->val);
                        if(node->right != NULL){
                            stackZig.push(node->right);
                        }
                        if(node->left != NULL){
                            stackZig.push(node->left);
                        }
                    }
                }
                result.push_back(levelResult);
                bForward = !bForward;
            }
            return result;
        }
    

Log in to reply
 

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