My c++ code using one queue and level flag


  • 2
    L
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if(!root)
            return res;
        vector<int> vlevel;
        queue<TreeNode*> q;
        q.push(root);
        int level1=1,level2=0;
        while(!q.empty()){
            TreeNode* front = q.front();
            q.pop();
            vlevel.push_back(front->val);
            if(front->left){
                q.push(front->left);
                ++level2;
            }
            if(front->right){
                q.push(front->right);
                ++level2;
            }
            
            
            if(--level1 == 0){//one level is over
                res.push_back(vlevel);
                level1 = level2;//next level
                level2=0;//next next level start
                vlevel.clear();
            }
            
        }
        reverse(res.begin(),res.end());
        return res;
    }

  • 0
    S

    why it's not working if i write
    if(level1==0)
    in third if statement.....:)


  • 0
    L

    @saurabhjat142
    the solution will be ok if you decrease level1 before the third if statement and write codes as you have given.
    --level1 stands for we have traversed one node of current level.
    Details are as following:
    level1 stands for the number of current level nodes.
    level2 stands for next level nodes number of current level.
    so,level1=1 when we begin to traverse the tree from the root.
    we will increase the level2 if left child or right child is not null.
    and decrease the level1 because we have traverse the one node of current level.
    the condition of if (--level1 == 0) stands for ending traversal of one level
    and next level traversal will begin so we swap the level1 and level2.


Log in to reply
 

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