【二叉树层序遍历】【队列】Leetcode 102 107 199 637 429 515 116 117 104 111

【二叉树层序遍历】【队列】Leetcode 102 107 199 637 429 515 116 117

    • 102. 二叉树的层序遍历解法 用队列实现
    • 107. 二叉树的层序遍历 II解法
    • 199. 二叉树的右视图 解法
    • 637. 二叉树的层平均值 解法
    • 429. N叉树的层序遍历
    • 515. 在每个树行中找最大值
    • 116. 填充每个节点的下一个右侧节点指针
    • 117. 填充每个节点的下一个右侧节点指针 II
    • 104. 二叉树的最大深度
    • 111. 二叉树的最小深度

---------------🎈🎈102. 二叉树的层序遍历 题目链接🎈🎈-------------------
---------------🎈🎈107. 二叉树的层序遍历 II 题目链接🎈🎈-------------------

---------------🎈🎈199. 二叉树的右视图 题目链接🎈🎈-------------------
---------------🎈🎈637. 二叉树的层平均值 题目链接🎈🎈-------------------
---------------🎈🎈429. N叉树的层序遍历 题目链接🎈🎈-------------------
---------------🎈🎈515. 在每个树行中找最大值 题目链接🎈🎈-------------------

---------------🎈🎈116. 填充每个节点的下一个右侧节点指针 题目链接🎈🎈-------------------
---------------🎈🎈117. 填充每个节点的下一个右侧节点指针 II 题目链接🎈🎈-------------------

---------------🎈🎈104. 二叉树的最大深度 题目链接🎈🎈-------------------
---------------🎈🎈111. 二叉树的最小深度 题目链接🎈🎈-------------------

102. 二叉树的层序遍历解法 用队列实现

在这里插入图片描述
在这里插入图片描述

时间复杂度O(N)
空间复杂度O(N)

import com.sun.source.tree.Tree;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) { 
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) return result;
        Queue<TreeNode> myqueue = new LinkedList<>();
        myqueue.add(root);

        while(!myqueue.isEmpty()){
            List<Integer> tempres = new ArrayList<>();
            int size = myqueue.size(); // 获取当前层的节点数
            for(int i = 0; i< size; i++){
                TreeNode temp = myqueue.poll();
                tempres.add(temp.val);
                if(temp.left != null){
                    myqueue.add(temp.left);
                }
                if(temp.right != null){
                    myqueue.add(temp.right);
                }
            }
            result.add(tempres);
        }

        return result;
    }
}

107. 二叉树的层序遍历 II解法

在这里插入图片描述

在基础的层序遍历的基础上增加一个Collections.reverse（）翻转输出即可

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> myqueue = new LinkedList<>();
        if(root==null) return result;
        myqueue.add(root);
        while(!myqueue.isEmpty()){
            List<Integer> resulttemp = new ArrayList<>();
            int size = myqueue.size(); 
            for(int i = 0; i< size; i++){
                TreeNode temp = myqueue.poll();
                resulttemp.add(temp.val);
                if(temp.left != null) {
                    myqueue.add(temp.left);
                }
                if(temp.right != null) {
                    myqueue.add(temp.right);
                }
            }
            result.add(resulttemp);
        }
        Collections.reverse(result);
        return result;
    }
}

199. 二叉树的右视图 解法

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> myqueue = new LinkedList<>();
        if(root == null) return result;
        myqueue.add(root);
        while(!myqueue.isEmpty()){
            int size = myqueue.size();
            for(int i = 0; i<size; i++){
                TreeNode temp = myqueue.poll();
                if(temp.left!=null){
                    myqueue.add(temp.left);
                }
                if(temp.right!= null){
                    myqueue.add(temp.right);
                }
                if(i == size-1){
                    result.add(temp.val);
                }
            }
        }



        return result;
    }
}

637. 二叉树的层平均值 解法

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        Queue<TreeNode> myqueue = new LinkedList<>();
        if(root == null) return result;
        myqueue.add(root);
        while(!myqueue.isEmpty()){
            int size = myqueue.size(); //得到size：当前层节点数
            double sum = 0;
            for(int i = 0; i<size; i++){ //弹出并得到size个节点的平均值，并将下一层的节点加入到队列
                TreeNode temp = myqueue.poll();
                sum += temp.val;
                if(temp.left != null){
                    myqueue.add(temp.left);
                }
                if(temp.right != null){
                    myqueue.add(temp.right);
                }

            }
            result.add(sum/size);
            
        }
        return result;

    }
}

429. N叉树的层序遍历

在这里插入图片描述

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

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

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<Node> myqueue = new LinkedList<>();
        if(root == null) return result;
        myqueue.add(root);
        while(!myqueue.isEmpty()){
            int size = myqueue.size();
            List<Integer> restemp = new ArrayList<>();
            for(int i = 0; i < size; i++){
                Node temp = myqueue.poll();
                restemp.add(temp.val); // 将值temp.val加入restemp
                for(Node node:temp.children){ // 遍历temp.chirdren 即为遍历每一个temp的子节点，如果不为null就加入到列表中
                    if(node != null){
                        myqueue.add(node);
                    }
                }
            }
            result.add(restemp);

        }
        return result;

    }
}

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

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result  = new ArrayList<>();
        Queue<TreeNode> myqueue = new LinkedList<>();
        if(root == null) return result;
        myqueue.add(root);
        while(!myqueue.isEmpty()){
            int size = myqueue.size();
            int max = (int)Math.pow(-2, 31);
            for(int i = 0; i < size; i++){
                TreeNode temp = myqueue.poll();
                if(temp.left != null){
                    myqueue.add(temp.left);
                }
                if(temp.right != null){
                    myqueue.add(temp.right);
                }
                if(max < temp.val){
                    max = temp.val;
                }
            }
            result.add(max);
            
        }
        return result;

    }
}

116. 填充每个节点的下一个右侧节点指针

在这里插入图片描述

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        Queue<Node> myqueue = new LinkedList<>();
        if(root == null) return root;
        myqueue.add(root);
        while(!myqueue.isEmpty()){
            int size = myqueue.size();
            Node head = myqueue.peek();
            for (int i = 0; i <size; i++) {
                Node temp = myqueue.poll();
                if(temp != head){
                    head.next = temp;
                    head = head.next;
                }
                if(temp.left != null){
                    myqueue.add(temp.left);
                    myqueue.add(temp.right);
                }
            }
        }
        return root;
    }
}

117. 填充每个节点的下一个右侧节点指针 II

在这里插入图片描述

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        Queue<Node> myqueue = new LinkedList<>();
        if(root == null) return root;
        myqueue.add(root);
        while(!myqueue.isEmpty()){
            int size = myqueue.size();
            Node head = myqueue.peek();
            for(int i = 0; i <size; i++){
                Node temp = myqueue.poll();
                if(temp != head){
                    head.next = temp;
                    head = head.next;
                }
                if(temp.left != null){
                    myqueue.add(temp.left);
                }
                if(temp.right != null){
                    myqueue.add(temp.right);
                }
            }
        }  
        return root;       
    }
}

104. 二叉树的最大深度

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        // 层序遍历
        Queue<TreeNode> myqueue = new LinkedList<>();
        if(root == null) return 0;
        myqueue.add(root);
        int result = 0;
        while(!myqueue.isEmpty()){
            int size = myqueue.size();
            for(int i = 0; i < size; i++){
                TreeNode temp = myqueue.poll();
                if(temp.left != null){
                    myqueue.add(temp.left);
                }
                if(temp.right != null){
                    myqueue.add(temp.right);
                }
            }
            result +=1;
        }
        return result;

    }
}

111. 二叉树的最小深度

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        // 层序遍历
        Queue<TreeNode> myqueue = new LinkedList<>();
        if(root == null) return 0;
        myqueue.add(root);
        int result = 0;
        while(!myqueue.isEmpty()){
            int size = myqueue.size();
            for(int i = 0; i < size; i++){
                TreeNode temp = myqueue.poll();
                if(temp.left != null){
                    myqueue.add(temp.left);
                }
                if(temp.right != null){
                    myqueue.add(temp.right);
                }
                if(temp.left == null && temp.right==null){
                    return result+1;
                }
            }
            result +=1;
        }
        return result;

    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/400421.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

如何用微软画图把1280X720的图片压缩成4:3?

如何用微软画图把1280X720的图片压缩成4:3?

最近在看20多年前的电视剧&#xff0c;视频截图是1280X720&#xff0c;比例失调。 如何压缩成4:3&#xff1f; 4 / 3 W / 720 W 720 X 4 / 3 960 打开画图&#xff0c;调整大学和扭曲&#xff08;Ctrl W&#xff09;&#xff0c;依据选择像素&#xff0c;取消保持纵横比…
阅读更多...
JVM原理学习

JVM原理学习

一.栈上的数据存储P95 二.堆上的数据存储 标记字段 指针压缩(节省空间 内存对齐(提高CPU缓存行效率 字段重排列方便内存对齐 类排在基本类型之后 三.JIT实时编译 优化手段 C2编译器&#xff0c;直接将循环相加求和优化为乘法。 方法内联 逃逸分析 四.G1垃圾回收器原理 年轻代…
阅读更多...
【学习总结】慢SQL治理经验总结

【学习总结】慢SQL治理经验总结

一、慢SQL定义 执行超过1s的SQL为慢SQL 三、慢SQl的风险 系统的响应时间延迟&#xff0c;影响用户体验 资源占用增加&#xff0c;增高了系统的负载&#xff0c;其他请求响应时间也可能会收到影响。 慢SQL占用数据库连接的时间长,如果有大量慢SQL查询同时执行&#xff0c;可能…
阅读更多...
阿里云 OSS

阿里云 OSS

阿里云对象存储服务&#xff08;Object Storage Service&#xff0c;简称 OSS&#xff09; OSS 为 Object Storage Service&#xff0c;即对象存储服务。是阿里云提供的海量、安全、低成本、高可靠的云存储服务。 OSS 具有与平台无关的 RESTful API 接口&#xff0c;可以在任…
阅读更多...
普中51单片机学习（定时器和计数器）

普中51单片机学习（定时器和计数器）

定时器和计数器 51单片机有两组定时器/计数器&#xff0c;因为既可以定时&#xff0c;又可以计数&#xff0c;故称之为定时器/计数器。定时器/计数器和单片机的CPU是相互独立的。定时器/计数器工作的过程是自动完成的&#xff0c;不需要CPU的参与。51单片机中的定时器/计数器是…
阅读更多...
内核移植学习

内核移植学习

内核移植 内核移植就是指将RT-Thread内核在不同的芯片架构、不同的板卡上运行起来。 移植可分为CPU架构移植和BSP板级支持包移植两部分。 CPU架构移植 在嵌入式领域有多种不同CPU架构&#xff0c;例如Cortex-M、ARM920T、MIPS32、RISC-V等等。 为了使RT-Thread能够在不同C…
阅读更多...
第三百五十九回

第三百五十九回

文章目录 1. 概念介绍2. 使用方法3. 代码与效果3.1 示例代码3.2 运行效果 4. 内容总结 013pickers2.gif 我们在上一章回中介绍了"如何实现Numberpicker"相关的内容&#xff0c;本章回中将介绍wheelChoose组件.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念…
阅读更多...
浅谈加密算法（对称加密、非对称加密、混合加密、数字签名、哈希函数）

浅谈加密算法（对称加密、非对称加密、混合加密、数字签名、哈希函数）

1、对称加密 对称加密只有一个密钥&#xff0c;直接使用这一个密钥对信息进行加密或解密。这样子就使得对称加密解密十分高效&#xff0c;计算量也相较于非对称加密小很多&#xff0c;适合有大量数据的场合。 密钥只有一个且他一定不能泄漏。由此分发密钥&#xff0c;讲这个密钥…
阅读更多...
MyBatis---初阶

MyBatis---初阶

一、MyBatis作用 是一种更简单的操作和读取数据库的工具。 二、MyBatis准备工作 1、引入依赖 2、配置Mybatis(数据库连接信息) 3、定义接口 Mapper注解是MyBatis中用来标识接口为Mapper接口的注解。在MyBatis中&#xff0c;Mapper接口是用来定义SQL映射的接口&#xff0c;通…
阅读更多...
Git 客户端可视化工具tortoisegit

Git 客户端可视化工具tortoisegit

Git 使用教程 git一点通 (kdocs.cn) 二、Git 客户端可视化工具-推荐 1.常用工具 tortoisegit 官网 https://tortoisegit.org/ 推荐 sourcetree 官网 https://www.sourcetreeapp.com/ 2.tortoisegit安装 2.1 下载安装包 2.2 下载语言包 2.3 安装 2.4 安装语言包 5.使用 5.1 新建…
阅读更多...
Puppeteer 使用实战：如何将自己的 CSDN 专栏文章导出并用于 Hexo 博客（一）

Puppeteer 使用实战：如何将自己的 CSDN 专栏文章导出并用于 Hexo 博客（一）

文章目录 效果展示说明利用工具整体思路Puppeteer 使用笔记保持登录状态打开新的页面点击 dialog跳转页面设置页面可见窗口大小寻找元素等待元素出现 整体代码 效果展示 说明 看了看网上很少做这个功能&#xff0c;但是我有这个需求&#xff0c;就抽出时间写了个简单的工具目前…
阅读更多...
opengl 学习着色器

opengl 学习着色器

一.GLSL 着色器是使用一种叫GLSL的类C语言写成的。GLSL着色器编码顺序&#xff1a;声明版本》定义输入输出》uniform》main函数。每个着色器的入口点是main函数&#xff0c;在main函数中我们处理所有的输入变量&#xff0c;并将结果输出到输出变量中。如下图&#xff1a; #ver…
阅读更多...
RocketMQ高可用架构涉及常用功能整理

RocketMQ高可用架构涉及常用功能整理

RocketMQ高可用架构涉及常用功能整理 1. 集群高可用系统架构和相关组件1.1 架构说明1.2 相关概念说明1.3 消息模型1.3.1 点对点模型1.3.2 发布订阅模型1.3.3 消息过滤 2. rocketmq的核心参数3. rocketmq常用命令4. 事务性4.1 数据写入流程4.2 数据读流程4.3 事务消息 5. 疑问和…
阅读更多...
QT_day2

QT_day2

1.思维导图 2.使用手动连接&#xff0c;将登录框中的取消按钮使用qt4版本的连接到自定义的槽函数中&#xff0c;在自定义的槽函数中调用关闭函数 将登录按钮使用qt5版本的连接到自定义的槽函数中&#xff0c;在槽函数中判断ui界面上输入的账号是否为"admin"&#xff…
阅读更多...
哈希应用 | 布隆过滤器概念 | 代码实现 | 哈希切割

哈希应用 | 布隆过滤器概念 | 代码实现 | 哈希切割

文章目录 1.布隆过滤器1.1.布隆过滤器的基本概念1.2.代码实现1.3.测试代码分析误判率1.4.布隆过滤器的优点1.5.关于几道面试题 关于位图&#xff1a;往期分析的 博客链接 1.布隆过滤器 1.1.布隆过滤器的基本概念 布隆过滤器的引出 位图使用1个比特位 直接定址法&#xff0c;…
阅读更多...
深入浅出JVM（一）之Hotspot虚拟机中的对象

深入浅出JVM（一）之Hotspot虚拟机中的对象

本篇文章思维导图 对象的创建 对象的创建可以分为五个步骤:检查类加载,分配内存,初始化零值,设置对象头,执行实例构造器 类加载检查 HotSpot虚拟机遇到一条new指令,会先检查能否在常量池中定位到这个类的符号引用,检查这个类是否类加载过 没有类加载过就去类加载类加载过就进…
阅读更多...
中国 AI 开课速度直逼美国 AI 颠覆性创新速度

中国 AI 开课速度直逼美国 AI 颠覆性创新速度

原文链接&#xff1a; 中国 AI 开课速度直逼美国 AI 颠覆性创新速度 今日热帖&#xff0c;有网友发帖称&#xff1a;Sora 和 ChatGPT 告诉我们&#xff0c;美国确实是遥遥领先&#xff0c;而且还越拉越远。 是不是遥遥领先暂且不说&#xff0c;但领先我们的确是事实。 主要是…
阅读更多...
多任务互斥及队列

多任务互斥及队列

一.互斥的引入 在FreeRTOS中&#xff0c;互斥&#xff08;Mutex&#xff09;是一种用于保护共享资源的机制。互斥锁可以确保同一时间只有一个任务能够访问共享资源&#xff0c;从而避免了竞态条件和数据不一致的问题。 FreeRTOS中互斥的引入方法&#xff1a; 创建互斥锁&#…
阅读更多...
【笔记】【算法设计与分析 - 北航童咏昕教授】绪论

【笔记】【算法设计与分析 - 北航童咏昕教授】绪论

算法设计与分析 - 北航童咏昕教授 文章目录 算法的定义定义性质 算法的表示自然语言编程语言伪代码 算法的分析算法分析的原则渐近分析 算法的定义 定义 给定计算问题&#xff0c;算法是一系列良定义的计算步骤&#xff0c;逐一执行计算步骤即可得预期的输出。 性质 有穷性确…
阅读更多...
【Linux】git操作 - gitee

【Linux】git操作 - gitee

1.使用 git 命令行 安装 git yum install git 2.使用gitee 注册账户 工作台 - Gitee.com 进入gitee&#xff0c;根据提示注册并登录 新建仓库 仓库名称仓库简介初始换仓库 3.Linux-git操作 进入仓库&#xff0c;选择“克隆/下载” 复制下面的两行命令进行git配置 然后将仓库clo…
阅读更多...
最新文章

Copyright @ 2022~2023