Simple BFS C++ 12ms soln


  • 0
    1
    class Solution {
        queue<TreeNode *> node;
        queue<int> lvl;
    public:
        vector<int> largestValues(TreeNode* root) {
    
            int prevLvl =0, currLvl =0, maxVal, pushed=0;
            TreeNode *tmp;
            vector<int>res;
            if (!root) return res;
            
            node.push(root);
            lvl.push(0);
            maxVal = root->val;
    
            while(!node.empty()) {
                tmp = node.front() ; node.pop();
                currLvl = lvl.front() ; lvl.pop();
                
                if(currLvl!=prevLvl) {
                    res.push_back(maxVal);                
                    prevLvl = currLvl;
                    maxVal = tmp->val;
                } else {
                    maxVal = (maxVal > tmp->val) ? maxVal : tmp->val;
                }
                
                if(tmp->left){
                    node.push(tmp->left);
                    lvl.push(currLvl+1);
                }
                
                if(tmp->right){
                    node.push(tmp->right);
                    lvl.push(currLvl+1);
                }
            }
            
            if((int)res.size()-1 < currLvl)
                res.push_back(maxVal);
                
            return res;
        }
    };
    

  • 0
    S

    I think mine is similar to you. I got the idea from "513Find Bottom Left Tree Value" .

    class Solution {
    public:
           vector<int> largestValues(TreeNode* root) {
            queue<TreeNode*> q;
            queue<int> level;
            
            vector<int> max;
            if(root == NULL){return max;}
            
            q.push(root);
            level.push(0);
            
            while(q.size()){
                // r: store the node
                TreeNode *r = q.front();q.pop();
                // l: store the depth of the node
                int l = level.front();level.pop();
                //when root go deeper by one step, l should plus 1
                if(r->left){q.push(r->left);level.push(l+1);}
                if(r->right){q.push(r->right);level.push(l+1);}
             
                if(max.size() < l+1){max.push_back(r -> val);}
                //max[i] compare the all the values of same row, and store the biggest number
                else if(max[l] < r -> val){max[l] = r -> val;}
            }
            return max;
        }
    };
    

    My English is not good. If anyone do not understand, you can post a question.


Log in to reply
 

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