LeetCode75| 二叉树-广度优先搜索

目录

199 二叉树的右视图

1161 最大层内元素和

199 二叉树的右视图

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int>res;
        if(root == NULL)return res;
        queue<TreeNode*>st;
        st.push(root);
        while(!st.empty()){
            int siz = st.size();
            for(int i = 0;i < siz;i++){
                TreeNode* cur = st.front();
                st.pop();
                if(cur->left != NULL)st.push(cur->left);
                if(cur->right != NULL)st.push(cur->right);
                if(i == siz - 1)res.push_back(cur->val);
            }
        }
        return res;
    }
};

时间复杂度O(n)

空间复杂度O(n)每个节点最多入栈一次?

1161 最大层内元素和

注意要返回的是层号

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        int res = -1e9 - 10;
        int ans = 0,mn = -1;
        if(root == NULL)return res;
        queue<TreeNode*>st;
        st.push(root);
        while(!st.empty()){
            int siz = st.size();
            int sum = 0;
            ans++;
            for(int i = 0;i < siz;i++){
                TreeNode* cur = st.front();
                st.pop();
                if(cur->left != NULL)st.push(cur->left);
                if(cur->right != NULL)st.push(cur->right);
                sum += cur->val;
            }
            if(sum > res){
                res = sum;
                mn = ans;
            }
        }
        return mn;
    }
};

时间复杂度O(n)

空间复杂度O(n)每个节点最多入栈一次?