【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅱ

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

Halo这里是Ppeua。平时主要更新C语言C++数据结构算法......感兴趣就关注我吧你定不会失望。

个人主页主页链接

算法专栏专栏链接

我会一直往里填充内容哒

LeetCode专栏专栏链接

目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目也会当天做完发出

代码仓库Gitee链接

点击关注=收获更多优质内容

题目:102. 二叉树的层序遍历

题解:

代码实现:

题目:2583. 二叉树中的第 K 大层和

题解:

代码实现:

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

题解:

代码实现:

完结撒花

今天的题目相较于昨天,增加了一点难度,但不用慌,我们一起来看看吧.

还不熟悉的朋友们可以看看我的二叉树专题,相信你定能有所收获

题目:102. 二叉树的层序遍历

题解:

什么是层序遍历呢?相较于前中后序的遍历方式,层序遍历是一层层的去遍历,例如这一题

那如何做到一层层遍历呢?

可以先将一个节点放入队列,每当取出一个节点的时候就将其左右非空节点放入队列中.

如此循环往复,当队列为空的时候,此时就将二叉树层序遍历完了.

所以我们需要一个队列来存储树的节点,那么如何知道这一层遍历完了呢?

我们可以在取出每次开始取出节点的时候,记录下此时队列内的数据个数,此时就是该层的节点个数.(可以看看上图)

(注意队列是头先出,从尾插入)每次插入的是非空节点

代码实现:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*>tree;
        vector<vector<int>>ans;
        if(root==NULL)return {};
        tree.push(root);
        int height=0;
        while(!tree.empty())
        {
            height=tree.size();
            ans.push_back(vector<int>());
            for(int i=1;i<=height;i++)
            {
                TreeNode*tmp=tree.front();
                tree.pop();
                ans.back().push_back(tmp->val);
                if(tmp->left)tree.push(tmp->left);
                if(tmp->right)tree.push(tmp->right);
            }            
        }
        return ans;
    }
};

题目:2583. 二叉树中的第 K 大层和

题解:

在有了上一题的基础下,这题就十分的简单啦,整体思想如下:先将每一层的值相加,然后放入容器当中,最后排个序,取出k-1层的即可.

具体的来看:层序遍历每一层的值,当遍历完这一层的时候,也就是size==0时,将这层的结果放入容器当中,最后通过lambda表达式实现从大到小排序,返回k-1层的结果(下标从0开始)

代码实现:

class Solution {
public:
    long long kthLargestLevelSum(TreeNode* root, int k) {
        queue<TreeNode*>tag;
        vector<long long>res;
        tag.push(root);
        while(!tag.empty())
        {
            int size=tag.size();
            int ans=0;
            for(int i=1;i<=size;i++)
            {
                TreeNode*tmp=tag.front();
                tag.pop();
                ans+=tmp->val;
                if(tmp->left)tag.push(tmp->left);
                if(tmp->right)tag.push(tmp->right);
            }
            res.push_back(ans);

        }
        sort(res.begin(),res.end(),[](auto const &c1,auto const &c2){
            return c1>=c2;
        });
        if(res.size()<k)return -1;
        else return res[k-1];

    }
};

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

题解:

这里有两种方法(深度优先搜索与广度优先搜索)其实也就是前序遍历与层序遍历,层序遍历这里简单提一下.与上面的大同小异就不过多赘述了:依旧是遍历出每一层最大的值,将其放入数组即可.

深度优先搜索:先看看基础情况若当前遍历到的值等于size,则说明这一层还没有元素被放入到容器当中,此时直接放入遍历到的元素即可,若反之,则取容器中对应层的元素与现在要放入的元素比较取最大值即可.

代码实现:

class Solution0 {//dfs
public:
    void preorder(TreeNode*root,vector<int>&res,int pi)
    {
        if(pi==res.size())
        {
            res.push_back(root->val);
        }else
        {
            res[pi]=max(res[pi],root->val);
        }
        if(root->left)
        {
            
            preorder(root,res,pi+1);
        }
        if(root->right)
        {
            preorder(root, res,pi+1);
        }

    }
    vector<int> largestValues(TreeNode* root) {
        int i=0;
        if(!root)return {};
        vector<int>res;
        preorder(root,res,0);
        return res;
    }
};
    
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*>tree;
        vector<int>ans;
        if(root==NULL)return {};
        tree.push(root);
        int height=0;
        
        while(!tree.empty())
        {
            int Max=INT_MIN;
            height=tree.size(); 
            for(int i=1;i<=height;i++)
            {
                TreeNode*tmp=tree.front();
                tree.pop();
                Max=max(Max,tmp->val);
                if(tmp->left)tree.push(tmp->left);
                if(tmp->right)tree.push(tmp->right);
            }
            ans.push_back(Max);
        }
        return ans;
    }
};