首页 > 编程语言 >Offer必备算法20_队列_宽搜bfs_四道力扣题详解(由易到难)

Offer必备算法20_队列_宽搜bfs_四道力扣题详解(由易到难)

时间:2024-04-01 23:02:04浏览次数:33  
标签:right TreeNode val Offer int 由易到难 nullptr 20 left

目录

①力扣429. N 叉树的层序遍历

解析代码

②力扣103. 二叉树的锯齿形层序遍历

解析代码

③力扣662. 二叉树最大宽度

解析代码

④力扣515. 在每个树行中找最大值

解析代码

本篇完。


①力扣429. N 叉树的层序遍历

429. N 叉树的层序遍历

难度 中等

给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。

树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。

示例 1:

输入:root = [1,null,3,2,4,null,5,6]
输出:[[1],[3,2,4],[5,6]]

示例 2:

输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示:

  • 树的高度不会超过 1000
  • 树的节点总数在 [0, 10^4] 之间
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        
    }
};

解析代码

层序遍历即可,仅需多加一个变量,用来记录每一层结点的个数。

  • ① 让根节点先入队。
  • ② 记录当前队头后打印,并让队头出队,然后检测,如果孩子不为空就把孩子带进去。(上一层节点出队时带入下一层节点入队)
  • ③ 只要队列不为空就说明还没完。如果队列为空,说明下面最后一层没有节点,遍历结束。
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret;
        if(root == nullptr)
            return ret;
        queue<Node*> q;
        q.push(root);
        while(!q.empty())
        {
            int sz = q.size();
            vector<int> tmp(sz); // 统计本层结点
            for(int i = 0; i < sz; ++i)
            {
                Node* t = q.front();
                q.pop();
                tmp[i] = t->val;
                for(auto& child : t->children) // 遍历下层孩子结点入队
                {
                    if(child != nullptr)
                        q.push(child);
                }
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

②力扣103. 二叉树的锯齿形层序遍历

103. 二叉树的锯齿形层序遍历

难度 中等

给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[20,9],[15,7]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

提示:

  • 树中节点数目在范围 [0, 2000] 内
  • -100 <= Node.val <= 100
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

    }
};

解析代码

        在正常的层序遍历过程中,我们是可以把一层的结点放在一个数组中去的。 既然我们有这个数组,在合适的层数逆序就可以得到锯齿形层序遍历的结果,可以弄一个int level遍历,偶数层的时候逆序,也可以用一个bool flag标志,一层修改一次,这里用标志的写法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(root == nullptr)
            return ret;
        queue<TreeNode*> q;
        q.push(root);
        bool flag = false;
        while(!q.empty())
        {
            int sz = q.size();
            vector<int> tmp(sz); // 统计本层结点
            for(int i = 0; i < sz; ++i)
            {
                TreeNode* t = q.front();
                q.pop();
                tmp[i] = t->val;
                // 下层孩子结点入队
                if(t->left != nullptr)
                    q.push(t->left);
                if(t->right != nullptr)
                    q.push(t->right);
            }
            if(flag)
                reverse(tmp.begin(), tmp.end());
            ret.push_back(tmp);
            flag = flag == false ? true : false;
        }
        return ret;
    }
};

③力扣662. 二叉树最大宽度

662. 二叉树最大宽度

 难度 中等

给你一棵二叉树的根节点 root ,返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点(即,两个端点)之间的长度。将这个二叉树视作与满二叉树结构相同,两端点间会出现一些延伸到这一层的 null 节点,这些 null 节点也计入长度。

题目数据保证答案将会在  32 位 带符号整数范围内。

示例 1:

输入:root = [1,3,2,5,3,null,9]
输出:4
解释:最大宽度出现在树的第 3 层,宽度为 4 (5,3,null,9) 。

示例 2:

输入:root = [1,3,2,5,null,null,9,6,null,7]
输出:7
解释:最大宽度出现在树的第 4 层,宽度为 7 (6,null,null,null,null,null,7) 。

示例 3:

输入:root = [1,3,2,5]
输出:2
解释:最大宽度出现在树的第 2 层,宽度为 2 (3,2) 。

提示:

  • 树中节点的数目范围是 [1, 3000]
  • -100 <= Node.val <= 100
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {

    }
};

解析代码

        第一种思路(会超过内存限制): 既然统计每一层的最大宽度,我们优先想到的就是利用序遍历,把当前层的结点全部存在队列里面,利用队列的长度来计算每一层的宽度,统计出最大的宽度。 但是由于空节点也是需要计算在内的。因此可以选择将空节点也存在队列里面。 这个思路是我们正常会想到的思路,但是极端境况下,最左边一条长链,最右边一条长链,需要存几亿个空节点,会超过最大内存限制。

第二种思路(利用二叉树的顺序存储 - 通过根节点的下标,计算左右孩子的下标):

        依旧是利用层序遍历,但是这一次队列里面不单单存结点信息,并且还存储当前结点如果在数组中存储所对应的下标(学习数据结构:堆的时候,学过计算左右孩子的方式)。

        这样我们计算每一层宽度的时候,无需考虑空节点,只需将当层结点的左右结点的下标相减再加 1 即可,因为要用左右结点,所以可以考虑用vector数组模拟queue队列。

        但是这里有个细节问题:如果二叉树的层数非常恐怖的话,任何一种数据类型都不能存下下标的值。但是没有问题,因为数据的存储是一个环形的结构。并且题目说明,数据的范围在 int 这个类型的最大值的范围之内,因此不会超出一圈。因此,如果是求差值的话,我们无需考虑溢出的情况。(用unsigned int即可)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        vector<pair<TreeNode*, unsigned int>> q; // ⽤数组模拟队列,结点+下标
        q.push_back({root, 0}); // 数组右边进,左边出
        unsigned int ret = 0;
        while(!q.empty())
        {
            // 先更新这⼀层的宽度
            auto& [x1, y1] = q[0];
            auto& [x2, y2] = q.back();
            ret = max(ret, y2 - y1 + 1);

            vector<pair<TreeNode*, unsigned int>> tmp; // 下层非空结点入队,直接替换即可
            for(auto& [x, y] : q) // 获取 结点+下标
            {
                if(x->left != nullptr)
                    tmp.push_back({x->left, y * 2 + 1});
                if(x->right != nullptr)
                    tmp.push_back({x->right, y * 2 + 2});
            }
            q = tmp;
        }
        return ret;
    }
};

④力扣515. 在每个树行中找最大值

515. 在每个树行中找最大值

难度 中等

给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。

示例1:

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2:

输入: root = [1,2,3]
输出: [1,3]

提示:

  • 二叉树的节点个数的范围是 [0,10^4]
  • -2^31 <= Node.val <= 2^31 - 1
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {

    }
};

解析代码

        层序遍历过程中,在执行让下一层节点入队的时候,我们是可以在循环中统计出当前层结点的最大值的。 因此可以在 bfs 的过程中,统计出每一层结点的最大值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> ret;
        if(root == nullptr)
            return ret;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            int sz = q.size(), maxVal = INT_MIN;
            while(sz--)
            {
                TreeNode* t = q.front();
                maxVal = max(maxVal, t->val);
                q.pop();
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
            ret.push_back(maxVal);
        }
        return ret;
    }
};

本篇完。

下一篇动态规划类型的是回文串dp类型的OJ。

下下篇是优先级队列_堆类型的OJ。

标签:right,TreeNode,val,Offer,int,由易到难,nullptr,20,left
From: https://blog.csdn.net/GRrtx/article/details/136615326

相关文章

  • GitHub上标星120k的Java进阶面试教程等!(建议收藏
    转发+关注,然后私信回复关键字“888”即可获得我精心整理的《Java开源项目合集》资料八、《JavaFamily》==============【互联网一线大厂面试+学习指南】进阶知识完全扫官。 部分目录:九、《interview_internal_reference》==================================2......
  • 2024最新分享我的面经总结:Java面试技术点攻略(九大核心专题
    关于操作系统这一部分,其实问的内容并不多,主要是因为这一部分问来问去也都是那么几个同样的问题,例如线程通信,线程与进程区别,进程调度算法以及虚拟内存、物理内存等。所以,在这一方面,我也整理了一些相对核心的内容。核心三:MySQL=========MySQL就更不用多说了,数据库不问......
  • 2024最新一线互联网大厂常见高并发面试题解析
    面试官:临界区是什么?答:临界区用来表示一种公共资源或者说是共享资源,可以被多个线程使用。但是每一次,只能有一个线程使用它,一旦临界区资源被占用,其他线程要想使用这个资源,就必须等待。比如,在一个办公室里有一台打印机,打印机一次只能执行一个任务。如果小王和小明同时需要打......
  • 2024JAVA互联网各大BATJ大厂(网易、华为
    ​为什么报了这个部门?​你觉得自己有什么优势,能给这个部门带来什么?​讲自己的三个优点?​说一下自己的不足?​。。。今日头条(抖音,收到意向书)​牛客网视频平台面试,算法题在线编程一下午走完三面流程。不涉及部门面试,面试官说三轮面试都是统招的。​一面(约......
  • 2024/4/1
    所花时间:1小时代码行:70行博客量:1篇了解到的知识点:对Expression#2ofSELECTlistisnotinGROUPBYclauseandcontainsnonaggregatedcolumn'enroll.user_information.user_class'whichisnotfunctionallydependentoncolumnsinGROUPBYclause;thisisincompa......
  • YOLOv9有效改进专栏汇总|未来更新卷积、主干、检测头注意力机制、特征融合方式等创新![
    ​专栏介绍:YOLOv9改进系列|包含深度学习最新创新,助力高效涨点!!!专栏介绍    YOLOv9作为最新的YOLO系列模型,对于做目标检测的同学是必不可少的。本专栏将针对2024年最新推出的YOLOv9检测模型,使用当前流行和较新的模块进行改进。本专栏于2024年2月29日晚创建,预计四......
  • Ubuntu20.04如何永久修改同一时间打开文件数上限以及解决Too many open files问题
       近期遇到一个问题,写的代码同一时间维护的tcp链接过多,导致linux的文件句柄达到上限,出现Toomanyopenfiles的问题。网上大多回答混乱,在这里做个总结,提醒日后使用。1.查看命令ulimit-a2.临时的修改,关闭终端失效ulimit-n204800或ulimit-SHn204800  //S代......
  • 2024.4.1
    2024.4.1【今天为什么是愚人节?因为四月是你的谎言】Monday二月二十三今天愚人节快乐赛(太快乐了A.项链题目描述有一天,达达捡了一条价值连城的宝石项链,但是,一个严重的问题是,他并不知道项链的主人是谁!在得知此事后,很多人向达达发来了很多邮件,都说项链是自己的,要求他归还(显......
  • EC-Final 2023 & CCPC Final 2023 游记
    由于去年打的不错(+运气比较好),能去两个Final打打旅游,最后都铜了,没铁也算能接受毕竟单论实力确实打不过其他学校的一二队。EC-Final时间地点:2024.1.12-1.14,上海过去的有点久,可能有些记不太清楚的地方。开场过了几分钟有人过B,我们几个去看B,想了一会胡了一个不是很简单的dp......
  • 【Java跳槽面试必备】2024年最新八股文
    【前言】网上各种面试八股文太多太多,但我今年找了好几个都是很久很久以前的老面试题,老文档了,和我出去面试市场上面试官问的问题基本上不一样了,可以说被打了一个措手不及,浪费了好几个机会,回来又找了好一些资料,以及结合自己最近的面试情况总结了一些心得免费分享给大家!虽然只有几本......