草庐IT

力扣107 二叉树的层序遍历

PersistentYg 2023-03-28 原文

力扣107 二叉树的层序遍历

题目：

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

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

示例 2：

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

示例 3：

输入：root = []
输出：[]

提示：

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

解题思路：

首先定义一个队列然后将根节点放入到队列中 获取队列的size然后再根据size循环获取到队列的值然后判断该节点有无左子树如果有左子树就先将左子树放入队列然后再将右子树放入队列。具体实现代码如下：

代码：

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树的层序遍历：就是遍历一棵二叉树层序遍历 依次返回从底层到顶层的节点
 * 核心思想：1)准备一个队列取出此时队列的size
 * 2)弹出节点如果该节点有左节点就先将左节点加入队列再将右节点加入队列，此操作循环size次
 */
public class LevelOrderBottom {
    //1.首先定义一个表示二叉树节点类型的类
    public static class TreeNode{
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    /**
     * 定义一个方法层序遍历二叉树并返回从底层到顶层每层的节点的值
     * 我们将每一层作为一个List的元素而每一个元素又是一个List这个List里面就是每一层的节点的值
     * 所以返回类型为List<List<Integer>>
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root){
        //2.1首先定义一个list便于最后返回
        List<List<Integer>> ans = new LinkedList<>();
        //2.2如果根节点为空就返回ans 此时ans为空
        if (root == null) {
            return ans;
        }
        //2.3定义一个队列 并首先将根节点放入队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        /*
        2.4下面就是循环直到queue为空，先取出queue的size然后根据size循环取出queue的值加入新建的LinkedList中再判断取出节点
        有无左子树如果有就先将左子树加入queue再将右子树节点加入queue，直到i不小于size意思也就是这一层全部取出完了，将这一层全部
        取出完的节点的值都加入到了LinkedList中形成一个链表，又因为要从底层到顶层取出所以每次我们都将新形成的链表加入到ans（ans本身
        也是一个链表）的0位置就成了倒序
         */
        while (!queue.isEmpty()){
            //2.4.1首先取出queue的size
            int size = queue.size();
            //2.4.2再定义一个链表这个链表就是用来存储每一层节点的值
            List<Integer> curAns = new LinkedList<>();
            //2.4.3根据size循环先取出queue的一个值将它加入到curAns有左子树就先将左子树加入到queue再将右子树加入到queue
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = queue.poll();
                curAns.add(treeNode.value);
                if(treeNode.left != null){
                    queue.add(treeNode.left);
                }
                if (treeNode.right != null){
                    queue.add(treeNode.right);
                }

            }
            //2.5因为要从底层到顶层展示每层节点的值又因为ans本身是一个链表所以每次我们将新形成的链表加入到ans的0位置
            ans.add(0,curAns);
        }
        //2.6最后返回ans
        return ans;
    }
}
107力扣queuecode先将算法与数据结构

有关力扣107 二叉树的层序遍历的更多相关文章

  1. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  2. 【Java入门】使用Java实现文件夹的遍历 - 2

    遍历文件夹我们通常是使用递归进行操作，这种方式比较简单，也比较容易理解。本文为大家介绍另一种不使用递归的方式，由于没有使用递归，只用到了循环和集合，所以效率更高一些！一、使用递归遍历文件夹整体思路1、使用File封装初始目录，2、打印这个目录3、获取这个目录下所有的子文件和子目录的数组。4、遍历这个数组，取出每个File对象4-1、如果File是否是一个文件，打印4-2、否则就是一个目录，递归调用代码实现publicclassSearchFile{publicstaticvoidmain(String[]args){//初始目录Filedir=newFile("d:/Dev");Datebeg

  3. ruby - Chef Ruby 遍历 .erb 模板文件中的属性 - 2

    所以这可能有点令人困惑，但请耐心等待。简而言之，我想遍历具有特定键值的所有属性，然后如果值不为空，则将它们插入到模板中。这是我的代码:属性:#===DefaultfileConfigurations#default['elasticsearch']['default']['ES_USER']=''default['elasticsearch']['default']['ES_GROUP']=''default['elasticsearch']['default']['ES_HEAP_SIZE']=''default['elasticsearch']['default']['MAX_OP

  4. ruby - 如何遍历 Ruby 中所有正则表达式匹配的字符串？ - 2

    我们有一个字符串:“”这个正则表达式://i如何从当前字符串中获取所有匹配项？ 最佳答案 "".scan(//)参见scan在ruby​​-docs上 关于ruby-如何遍历Ruby中所有正则表达式匹配的字符串？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/6857852/

  5. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  6. ruby - 循环遍历数组的元素 - 2

    我想从0到2循环@a:0,1,2,0,1,2。defset_aif@a==2@a=0else@a=@a+1endend也许有更好的方法？ 最佳答案 (0..2).cycle(3){|x|putsx}#=>0,1,2,0,1,2,0,1,2item=[0,1,2].cycle.eachitem.next#=>0item.next#=>1item.next#=>2item.next#=>0... 关于ruby-循环遍历数组的元素，我们在StackOverflow上找到一个类似的问题：

  7. ruby-on-rails - 如何在 Rails View 中遍历数组？ - 2

    我在MySql中进行了查询，但在Rails和mysql2gem中工作。信息如下:http://sqlfiddle.com/#!2/9adb8/6查询工作正常，没有问题，并显示以下结果:UNITV1A1N1V2A2N2V3A3N3V4A4N4V5A5N5LIFE200120000000000ROB010012000000000-为rails2.3.8安装了mysql2gemgeminstallmysql2-v0.2.6-创建Controller:classPolicyController这是日志:SQL(0.9ms)selectdistinct@sql:=concat('SELECTpb

  8. ruby - Ruby 中的目录遍历 - 2

    我一直在尝试使用简单的递归方法在Ruby中为一个更大的程序的一部分实现目录遍历。但是我发现Dir.foreach不包括其中的目录。我怎样才能列出它们？代码:defwalk(start)Dir.foreach(start)do|x|ifx=="."orx==".."nextelsifFile.directory?(x)walk(x)elseputsxendendend 最佳答案 问题是每次递归，你传递给File.directory?的路径isno只是实体(文件或目录)名称；所有上下文都丢失了。所以说你进入one/two/three/检

  9. ruby - 遍历目录和子目录中的每个 .jpg 或 .jpeg 文件 - 2

    我想遍历目录中的每个jpg/jpeg文件以及每个子目录和该子目录的每个子目录等等。我希望能够浏览文件夹中的每个图像文件。有没有一种简单的方法可以做到这一点，或者递归方法是否效果最好？ 最佳答案 Dir.glob("your_directory/**/*.{jpg,jpeg}") 关于ruby-遍历目录和子目录中的每个.jpg或.jpeg文件，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questi

  10. Ruby 的 "each"方法没有遍历数组中的所有项目？ - 2

    我正在尝试以下代码:a=[1,2,3,4]a.eachdoputs"Removing#{a.last}"a.popend但我并没有弹出所有四个数字，而是只弹出了前3个数字。实际上，执行类似putsa.length的操作会返回1并且puts-ing显示元素“1”仍然存在。我需要如何正确使用该方法？(我正在使用Ruby2.0)。 最佳答案 我怀疑发生这种情况是因为您在修改列表时迭代了列表的元素。尝试以下操作:a=[1,2,3,4]untila.empty?doputs"Removing#{a.last}"a.popend

随机推荐