Sharing my 6 ms iterative solution using queues with end of level identified as NULL.


  • 0
    C
    class Solution {
    

    public:
    vector<int> rightSideView(TreeNode* root) {

        vector<int> v;
        queue<struct TreeNode *> q;
        struct TreeNode *ptr=NULL,*prev=NULL;
        
        if(root == NULL)
        return v;
        
        q.push(root);
        q.push(NULL);  //End of level is identified with NULL
        
        while(!q.empty())
        {
            prev = ptr;  //when ptr becomes NULL, prev will point to node before NULL i.e the last node in the given level
            ptr = q.front();
            q.pop();
            
            if(ptr)
            {
                if(ptr->left)
                q.push(ptr->left);
                if(ptr->right)
                q.push(ptr->right);
            }
            else
            {
                if(!q.empty())
                     q.push(NULL);
                    
               v.push_back(prev->val); //push the last node in the given level
                
            }
        }
        
        return v;
        
    }
    

    };


Log in to reply
 

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