6ms C++ solution


  • 0
    X

    Use a "last" and "tail" to track the rightmost val in each level of the binary tree.

    class Solution {
    public:
    vector<int> rightSideView(TreeNode* root) {
        int last=0,tail=0;
        vector<int> solution;
        queue<TreeNode* > bfs;
        
        if(root==NULL)
           return solution;
           
        bfs.push(root);
        last=root->val;
        tail=root->val;
        
       
        
        while(bfs.size()!=0){
            TreeNode* v=bfs.front();
            bfs.pop();
            if(v->left!=NULL){
               bfs.push(v->left);
               tail=v->left->val;
            }
            if(v->right!=NULL){
                bfs.push(v->right);
                tail=v->right->val;
            }
            
            if(v->val==last){
                solution.push_back(v->val);
                last=tail;
            }
        }
        
        return solution;
        
    }
    

    };


  • 0
    M

    I have some questions with your solution.
    if(v->val==last){
    solution.push_back(v->val);
    last=tail;
    }
    consider the case followed

        1            
      /    \
    2       3
           /  \
          4    4
    

    your solution returns [1,3,4,4],but the answer should be [1,3,4]?
    Am I right?


  • 0
    X

    you are right. The node's val should be different.


Log in to reply
 

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