BFS C++ without reverse


  • 0
    Z

    BFS. Every two times, change whether left or right node to push into stack (implemented by using vector).

    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            // BFS
            vector<int> vc;
            vector<vector<int>> rt;
            vector<TreeNode*> tr1, tr2;
            if(!root)   return rt;
            tr1.push_back(root);
            
            while(!tr1.empty()){
                vc.clear();
                tr2.clear();
                for(int i=tr1.size()-1; -1<i; i--){
                    vc.push_back(tr1[i]->val);
                    if(tr1[i]->left)    tr2.push_back(tr1[i]->left);
                    if(tr1[i]->right)   tr2.push_back(tr1[i]->right);
                }
                rt.push_back(vc);
                
                if(tr2.empty()) return rt;
                vc.clear();
                tr1.clear();            
                for(int i=tr2.size()-1; -1<i; i--){
                    vc.push_back(tr2[i]->val);
                    if(tr2[i]->right)   tr1.push_back(tr2[i]->right);
                    if(tr2[i]->left)    tr1.push_back(tr2[i]->left);
                }      
                rt.push_back(vc);
            }
                
            return rt;
        }
    };
    

Log in to reply
 

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