数据结构与算法-二叉树-层次遍历I

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

二叉树层次遍历I

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

示例 1:

数据结构与算法-二叉树-层次遍历I,数据结构与算法,算法,数据结构

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

思路:提到层次遍历,首先想到的就是用队列,首先将头节点放入队列中,然后出队,将出队节点的左节点和右节点分别入队,一直重复该操作,直到队列为空。

但是该题要求输出要求每一层放到一个List中,所以需要在原有基础上,做一些调整。通过获取队列的大小,来判断哪些节点是在同一层

解题:

class Solution {
     public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) {
            queue.add(root);
        }
        while(!queue.isEmpty()) {
            List<Integer> arr = new ArrayList<>();
            int currenLvelSize = queue.size();
            for (int i = 1; i <= currenLvelSize; i++) {
                TreeNode poll = queue.poll();
                arr.add(poll.val);
                if(poll.left != null) {
                    queue.add(poll.left);
                }
                if(poll.right != null) {
                    queue.add(poll.right);
                }
            }
            res.add(arr);
        }
        return res;
    }
}

我最开始想到的思路就是在每一层结束的时候添加一个标记位,来表示该层的结束。实现代码如下:

个人觉得没什么问题,但是最终力扣判定超时。不知道为啥。文章来源地址https://www.toymoban.com/news/detail-812686.html

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) {
            queue.add(root);
            queue.add(new TreeNode(Integer.MAX_VALUE));
        }
        while(!queue.isEmpty()) {
            List<Integer> arr = new ArrayList<>();
            while (!queue.isEmpty() && queue.peek().val != Integer.MAX_VALUE) {
                TreeNode poll = queue.poll();
                arr.add(poll.val);
                if(poll.left != null) {
                    queue.add(poll.left);
                }
                if(poll.right != null) {
                    queue.add(poll.right);
                }
            }
            queue.add(new TreeNode(Integer.MAX_VALUE));
            if(arr.size()>0) {
                res.add(arr);
            }
            queue.poll();
        }
        
        return res;

    }

到了这里,关于数据结构与算法-二叉树-层次遍历I的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构与算法----详解二叉树的遍历(迭代、递归)

    ❤️ 作者简介 :大家好我是小鱼干儿♛是一个热爱编程、热爱算法的大三学生,蓝桥杯国赛二等奖获得者 🐟 个人主页 :https://blog.csdn.net/qq_52007481 ⭐ 个人社区 :【小鱼干爱编程】 🔥 算法专栏 :算法竞赛进阶指南 💯 刷题网站 :虽然市面上有很多的刷题网站,但是里面

    2024年01月24日
    浏览(54)
  • 【夜深人静学数据结构与算法 | 第四篇】手撕二叉树遍历

    目录 前言: 二叉树遍历方式: 手撕前中后序遍历(递归)的三大准备 深度优先搜索:  手撕前中后遍历(递归): 手撕前中后序遍历(迭代): 深度优先搜索: 总结:         今天我们将带领大家手撕二叉树的遍历,本篇会分别讲解深度优先搜索法和广度优先有搜索法下

    2024年02月09日
    浏览(51)
  • 二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”

    各位CSDN的uu们你们好呀,今天小雅兰的内容仍然是二叉树和Leetcode每日一题,下面,就让我们进入二叉树的世界吧!!! 这个题目需要重新定义一个函数,函数参数需要有左子树和右子树,题目所给定的函数无法解决问题。 每个不为空的结点,都可以认为是一棵子树的根 

    2024年02月16日
    浏览(46)
  • 【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :首先我们要知道后序遍历数组的最后一个元素必然是根节点,然后根据根节点在中序遍历数组中的位置进行划分,得到根节点的左右子树遍历数组,以此递归。当然这里有一个前提

    2024年02月10日
    浏览(41)
  • 【算法与数据结构】二叉树的三种遍历代码实现(下)—— 非递归方式实现(大量图解)

     上篇: 【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解_Hacynn的博客-CSDN博客 https://blog.csdn.net/zzzzzhxxx/article/details/133609612?spm=1001.2014.3001.5502 目录 前言 1、先序遍历 1.1、详细图解描述 1.2、先序遍历非递归代码实现  2、中序遍历 2.1、详细图解描

    2024年02月08日
    浏览(39)
  • 【数据结构与算法】二叉树的深度,节点数,第k层的节点数,遍历,二叉树叶节点的个数

        目录 一.前言 二.二叉树的节点数 二.二叉树的深度 三.二叉树第k层的节点数 四.二叉树的遍历 1.前序遍历 2.中序遍历 3.后序遍历 总结 4.层序遍历 五.二叉树叶节点的个数 我们需要 先构建个二叉树 ,方便后续对函数的测试; 还有我们在实现二叉树的这些函数时, 尽量少用

    2023年04月08日
    浏览(73)
  • 【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解

      本篇博客 (上篇) 先带大家学习 递归方式 进行三种遍历, 而在后续的 (下篇) 中将为大家详细讲解非递归的三种遍历方式。 目录 1、二叉树 2、二叉树的递归遍历 2.1、先序遍历 2.2、中序遍历 2.3、后序遍历  二叉树(Binary tree)是树形结构的一个重要类型。许多实际问

    2024年02月08日
    浏览(44)
  • 【数据结构】二叉树<遍历>

    在学习二叉树遍历之前我们先了解下二叉树的概念。 二叉树是: 1.空树 2.非空:根节点,根节点的左子树,根节点的右子树构造。 学习二叉树结构,最简单的方式就是遍历了。 二叉树的遍历就是按照某种特定的规则,依次对二叉树中的结点进行相应的操作,并且每个节点只

    2023年04月11日
    浏览(61)
  • 【数据结构】二叉树(遍历,递归)

     🌈个人主页: 秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 ​​​ 目录 二叉树遍历规则 前序遍历 ​ 中序遍历  后序遍历 递归结构遍历 前序 中序  求节点个数 求叶子节点个数  求树

    2024年01月19日
    浏览(41)
  • 【数据结构】二叉树的遍历

      Yan-英杰的主页 悟已往之不谏 知来者之可追    C++程序员,2024届电子信息研究生 目录 前序、中序以及后序遍历 前序遍历 中序遍历 后序遍历                  学习二叉树结构,最简单的方式就是遍历。所谓 二叉树遍历 (Traversal) 是按照某种特定的规则,依次对二叉

    2023年04月23日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包