The 15th day of the special assault version of the sword offer

剑指 Offer II 044. 二叉树每层的最大值

简单的层序遍历

class Solution {
    
public:
    vector<int> largestValues(TreeNode* root) {
    
        if(!root) return {
    };
        queue<TreeNode*> que;
        que.push(root);
        vector<int> res;
        while(que.size()) {
    
            int sz = que.size();
            int maxx = INT_MIN;
            for(int i = 0; i < sz; i++) {
    
                auto cur = que.front(); que.pop();
                maxx = max(maxx,cur->val);
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            res.push_back(maxx);
        }
        return res;
    }
};

---

剑指 Offer II 045. 二叉树最底层最左边的值

层序遍历,Each time a layer sequence is recorded, if there is a next layer, the current sequence will be cleared and the next layer sequence will be recorded,Finally, the first one returned is the bottom leftmost node

class Solution {
    
public:
    int findBottomLeftValue(TreeNode* root) {
    
        queue<TreeNode*> que;
        que.push(root);
        vector<int> backup;
        while(que.size()){
    
            int sz = que.size();
            backup.clear();
            for(int i = 0; i < sz; i++) {
    
                auto cur = que.front(); que.pop();
                backup.push_back(cur->val);
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return backup[0];
    }
};

---

剑指 Offer II 046. 二叉树的右侧视图
The layer order traversal records the last one of each layer

class Solution {
    
public:
    vector<int> rightSideView(TreeNode* root) {
    
        if(!root) return {
    };
        que<TreeNode*> que;
        que.push(root);
        vector<int> res;
        while(que.size()) {
    
            int last = -1, sz = que.size();
            for(int i = 0; i < sz; i++) {
    
                auto cur = que.front(); que.pop();
                last = cur->val;
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            res.push_back(last);
        }
        return res;
    }
};