【C++】102.二叉树的层序遍历

这篇具有很好参考价值的文章主要介绍了【C++】102.二叉树的层序遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

  • 给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

示例1:

【C++】102.二叉树的层序遍历,Leetcode/牛客网,c++,数据结构,二叉树

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

示例 2:

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

示例 3:

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

提示:

  • 树中节点数目在范围 [0, 2000]
  • -1000 <= Node.val <= 1000

思路分析

这个问题实际上可以只用一个队列就实现,只需要再增加一个变量levelSize,用来记录每一层的数据个数,然后再让这个队列一层一层的出去。之前的方法中,实际上队列并不是一层一层出去的,它有可能队列里面同时有两层的数据,我们以下面这个图来解释一下原因:

【C++】102.二叉树的层序遍历,Leetcode/牛客网,c++,数据结构,二叉树

如果有两层队列实现的话,3这个节点出来的时候,会让920这两个节点进入队列,而9这个节点出来的时候会让15这个节点进入队列,这个时候队列里面就同时有了第2层和第3层的数据。

所以我们想通过levelSize来达到一个目的:控制这个队列实现一层一层的出去。

那我们要怎么实现呢?我们仍然以刚才的图来进行分析:

3节点进入队列的时候,它的层数为1,由于它是根节点,所以它肯定只有一个,所以3就可以直接出队列。这个时候我们让levelSize进行自减操作它就变成了0,表示这一层已经出完了。

那么由于3节点出的时候会把920也带进来,也就是说当前层的节点全部出队列的时候一定是下一层的节点全部进入队列,这个时候我们将levelSize重新更新为第二层节点的数目也就是2,然后再进行出队列的操作:9节点出队列同时将15节点带进队列,然后levelSize自减变为120节点出队列同时将15节点和7节点带进队列,levelSize再自减变为0。这个时候就说明第二层也出完了。那么此时第三层都在队列里面所以我们再次更新levelSize的值为3,依次类推直到整棵树都被遍历完就实现了只用一个队列实现层序遍历。

那么根据以上的思路,我们就可以写出下面的代码:

完整代码

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        int levelSize = 0;
        if (root)//如果根不为空,就入队列
        {
            q.push(root);
            levelSize = 1;
        }

        vector<vector<int>> vv;//用来存放一层一层出的节点
        while (!q.empty())//如果队列不等于空,就说明树还没有被遍历完
        {
            //通过levelSize控制一层一层出
            vector<int> v;//用来存放每一层的数据
            while (levelSize--)//levelSize是几循环就执行几次,--levelSize表示的则是执行(levelSize - 1)次
            {
                TreeNode* front = q.front();//先取队头的数据
                q.pop();
                v.push_back(front->val);
                //进去的同时把该节点的下一层往队列里面带

                if (front->left)//左如果不为空就让左入队列
                    q.push(front->left);

                if (front->right)//右如果不为空就让右入队列
                    q.push(front->right);

            }
            //走到这里就说明当前层已经出完了,就把当前层所出的数据放到vv里面
            vv.push_back(v);
            //更新下一层的数据
            levelSize = q.size();
        }

        return vv;
    }
};

运行结果
【C++】102.二叉树的层序遍历,Leetcode/牛客网,c++,数据结构,二叉树文章来源地址https://www.toymoban.com/news/detail-838606.html

到了这里,关于【C++】102.二叉树的层序遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • ★102. 二叉树的层序遍历

    很巧妙的,又学习了一种层次遍历的方法, 就是说根据当前的队列的长度去遍历,遍历的当前队列的长度就是该层次的节点个数。

    2024年02月05日
    浏览(43)
  • 每日一题 102二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例 1: 输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]] 示例 2: 输入:root = [1] 输出:[[1]] 示例 3: 输入:root = [] 输出:[] 提示: 树中节点数目在范围 [0, 2000] 内 -1000 =

    2024年02月09日
    浏览(44)
  • 代码随想录Day12 二叉树 LeetCode T102二叉树的层序遍历 T226 翻转二叉树 T101 对称二叉树

    本文思路和详细讲解来自于:代码随想录 (programmercarl.com) 题目链接:102. 二叉树的层序遍历 - 力扣(LeetCode) 本题使用队列辅助完成,讲解主要函数CheckOrder:首先判断root是否为空,是就直接返回,然后创建队列,向里加入root元素,计算队列的长度,也就是每一层的元素个数,while循环,si

    2024年02月06日
    浏览(44)
  • 每日一练:LeeCode-102、二又树的层序遍历【二叉树】

    本文是力扣LeeCode-102、二又树的层序遍历 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐LeeCode。 给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 ( 即逐层地,从左到右访问所有节点 )。 示例 1: 输入:root = [3,9,20,null,null,15,7] 输出:[[3

    2024年01月21日
    浏览(40)
  • LeetCode.107. 二叉树的层序遍历 II

    107. 二叉树的层序遍历 II 这个题目考查的是二叉树的层序遍历,对于二叉树的层序遍历,我们需要借助 队列 这种数据结构。再来回归本题 ,我们只需要将 二叉树的层序遍历的结果逆序,就可以得到这道题我们要求的答案了。接下来我们的难题就是 如何实现二叉树的层序遍

    2024年02月21日
    浏览(55)
  • leetcode做题笔记107. 二叉树的层序遍历 II

    给你二叉树的根节点  root  ,返回其节点值  自底向上的层序遍历  。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 本题要求二叉树的层序遍历,并且是从下至上的层序遍历,可以考虑先按照从上至下的层序遍历先将层序遍历结果放到数组中,再对每层

    2024年02月11日
    浏览(36)
  • 【Py/Java/C++三种语言详解】LeetCode每日一题240216【二叉树BFS】LeetCode103、二叉树的层序遍历II

    有LeetCode交流群/华为OD考试扣扣交流群可加: 948025485 可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1336 了解算法冲刺训练 LeetCode103、二叉树的锯齿形层序遍历 给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进

    2024年02月20日
    浏览(38)
  • 41 二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 提示: 树中节点数目在范围 [0, 2000] 内 -1000 = Node.val = 1000

    2024年02月07日
    浏览(46)
  • 二叉树题目:二叉树的层序遍历 II

    标题:二叉树的层序遍历 II 出处:107. 二叉树的层序遍历 II 4 级 要求 给你二叉树的根结点 root texttt{root} root ,返回其结点值自底向上的层序遍历(即从左到右,按从叶结点所在层到根结点所在层逐层遍历)。 示例 示例 1: 输入: root   =   [3,9,20,null,null,15,7] texttt{root = [3

    2024年02月11日
    浏览(35)
  • day-20 二叉树的层序遍历

    思路:利用队列进行广度优先遍历即可 注意点:ArrayList执行remove之后,索引i会立即重排,注意可能越界 code:

    2024年03月19日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包