代码随想录打卡第十三天--补附加题

代码随想录–二叉树部分

day14 二叉树第二天
补一下昨天层序遍历的十个题

一、力扣107–二叉树的层序遍历Ⅱ

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if(!root) return {};
        vector<vector<int>> result;
        queue<TreeNode *> que;
        que.push(root);
        while(!que.empty())
        {
            int length = que.size();
            vector<int> temp;
            for(int i = 0; i < length; i ++)
            {
                TreeNode * curr = que.front(); que.pop();
                if(curr->left) que.push(curr->left);
                if(curr->right) que.push(curr->right);
                temp.push_back(curr->val);
            }
            result.push_back(temp);
        }
        vector<vector<int>> result_reverse;
        for(int i = result.size() - 1; i >= 0 ; i --)
        {
            result_reverse.push_back(result[i]);  // reverse the forward result to backward
        }
        return result_reverse;
    }
};

二、力扣199–二叉树的右视图

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root) return {};
        vector<int> result;
        queue<TreeNode *> que;
        que.push(root);
        while(!que.empty())
        {
            int length = que.size();
            for(int i = 0; i < length ; i ++)
            {
                TreeNode * curr = que.front(); que.pop();
                if(curr->left) que.push(curr->left);
                if(curr->right) que.push(curr->right);
                if(i == length - 1) result.push_back(curr->val); // only record the edge value
            }
        }
        return result;

    }
};

三、力扣637–二叉树的层平均值

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if(!root) return {};
        vector<double> result;
        queue<TreeNode *> que;
        que.push(root);
        while(!que.empty())
        {
            int length = que.size();
            vector<int> temp;
            for(int i = 0; i < length ; i ++)
            {
                TreeNode * curr = que.front(); que.pop();
                if(curr->left) que.push(curr->left);
                if(curr->right) que.push(curr->right);
                temp.push_back(curr->val);
            }
            double sum = 0;
            for(auto & ele : temp) sum += ele;
            result.push_back(sum/length*1.0);  // sum values and compute the average
        }
        return result;
    }
};

四、力扣429–N叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        if(!root) return {};
        vector<vector<int>> result;
        queue<Node *> que;
        que.push(root);
        while(!que.empty())
        {
            int length = que.size();
            vector<int> temp;
            for(int i = 0; i < length ; i ++)
            {
                Node * curr = que.front(); que.pop();
                for(auto child : curr->children) if(child) que.push(child); // N childen 
                temp.push_back(curr->val);
            }
            result.push_back(temp);
        }
        return result;    
    }
};

五、力扣515–在每个树行中找最大值

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if(!root) return {};
        vector<int> result;
        queue<TreeNode *> que;
        que.push(root);
        while(!que.empty())
        {
            int length = que.size();
            vector<int> temp;
            for(int i = 0; i < length ; i ++)
            {
                TreeNode * curr = que.front(); que.pop();
                if(curr->left) que.push(curr->left);
                if(curr->right) que.push(curr->right);
                temp.push_back(curr->val);
            }
            auto largest = max_element(temp.begin(), temp.end());
            result.push_back(*largest);
        }
        return result;
    }
};

六、力扣116–填充每个节点的下一个右侧节点指针

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;
        queue<Node *> que;
        que.push(root);
        while(!que.empty())
        {
            int length = que.size();
            
            for(int i = 0; i < length ; i ++)
            {
                Node * curr = que.front(); que.pop();
                if(curr->left) que.push(curr->left);
                if(curr->right) que.push(curr->right);
                if(i == length - 1)curr->next = NULL;
                else curr->next = que.front();
            }
        }
        return root;      
    }
};

七、力扣117–填充每个节点的下一个右侧节点指针Ⅱ

代码同上

总结

基本上就是层序遍历的模板改改就能用，模板如下：

        if(!root) return;
        queue<Node *> que;
        que.push(root);
        while(!que.empty())
        {
            int length = que.size();
            for(int i = 0; i < length ; i ++)
            {
                Node * curr = que.front(); que.pop();
                if(curr->left) que.push(curr->left);
                if(curr->right) que.push(curr->right);
                /*Add function here*/
            }
        }
        return;