算法打卡day14|二叉树篇03|104.二叉树的最大深度、559.n叉树的最大深度、111.二叉树的最小深度、222.完全二叉树的节点个数

算法题

Leetcode  104.二叉树的最大深度

题目链接:104.二叉树的最大深度

大佬视频讲解:二叉树的最大深度视频讲解

个人思路

可以使用层序遍历,因为层序遍历会有一个层数的计算,最后计算到的层数就是最大深度;

解法
迭代法

就是层序遍历的模板代码,遍历节点的时候不用添加值,最后返回深度

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        //层序遍历
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;//计算深度
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
        }
        return depth;
    }
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(使用一个列表)

递归法

递归法也很简单,因为是计算树的最大深度,就把二叉树分为两边,各个计算深度取最大值即可。

本题可以使用前序(中左右),也可以使用后序遍历(左右中),使用前序求的就是深度,使用后序求的是高度力扣上的高度最低是1,也就是从1开始的;

  • 二叉树节点的深度:指从节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)
  • 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数或者节点数(取决于高度从0开始还是从1开始)
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);//计算左节点深度
        int rightDepth = maxDepth(root.right);//计算右节点深度
        return Math.max(leftDepth, rightDepth) + 1;//加一的原因是还有根节点
    }
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(使用一个结果子列表,和一个列表)


Leetcode 59.n叉树的最大深度

题目链接:59.n叉树的最大深度

个人思路

与上面二叉树的思路差不多,只不过二叉树是遍历左右子树,n叉树就是遍历n各节点

解法

递归法

方法与二叉树最大深度一样,只不过要比较各个节点下的深度

class Solution {
    /*后序遍历求root节点的高度*/
    public int maxDepth(Node root) {
        if (root == null) return 0;

        int depth = 0;
        if (root.children != null){
            for (Node child : root.children){
                depth = Math.max(depth, maxDepth(child));//各个孩子节点中最高的节点
            }
        }

        return depth + 1; //中节点
    }  
}

时间复杂度:O(n);(遍历二叉树)

空间复杂度:O(1);(使用常量)

迭代法

与二叉树类似,只修改了孩子节点的遍历放入。

class Solution {
    //使用层序遍历
    public int maxDepth(Node root) {
        if (root == null)   return 0;
        int depth = 0;
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty())
        {
            depth ++;//根节点深度加1
            int len = que.size();//每层元素
            while (len > 0)
            {
                Node node = que.poll();

                //对应二叉树层序遍历的左右节点
                for (int i = 0; i < node.children.size(); i++)
                    if (node.children.get(i) != null) 
                        que.offer(node.children.get(i));

                len--;
            }
        }
        return depth;//深度
    }
}

时间复杂度:O(n);(遍历二叉树)

空间复杂度:O(n);(使用队列)


Leetcode 111.二叉树的最小深度

题目链接:111.二叉树的最小深度

大佬视频讲解:二叉树的最小深度视频讲解

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明:叶子节点是指没有子节点的节点。

个人思路

也可以层序遍历,当第一次遍历到改节点没有左右孩子,那深度就是最小深度。

解法
迭代法

在原来层序遍历的基础上加个判断节点左右孩子是否为空的操作即可;

class Solution {
   //层序遍历
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();

        deque.offer(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();

                // 当第一次遍历到叶子结点,直接返回depth,因为从上往下遍历,所以该值就是最小值
                if (poll.left == null && poll.right == null) {
                    return depth;
                }

                if (poll.left != null) {
                    deque.offer(poll.left);
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                }
            }
        }
        return depth;
    }
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(使用队列)

递归法

注意在节点左孩子或右孩子 为空时的情况,这时深度要加1,看如下代码

class Solution {
    public int minDepth(TreeNode root) {1.确定递归函数的参数和返回值
        if (root == null) {2.确定终止条件
            return 0;
        }
        
        //3.确定单层递归的逻辑
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);

        if (root.left == null) {
            return rightDepth + 1;//原因如上图
        }
        if (root.right == null) {
            return leftDepth + 1;
        }

        // 左右结点都不为null
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(1);(使用临时节点)


Leetcode 222.完全二叉树的节点个数

题目链接:222.完全二叉树的节点个数

大佬视频讲解:完全二叉树的节点个数视频讲解

个人思路

将二叉树分为左子树和右子树,递归返回节点个数然后相加

解法
递归法
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        //还有个根节点所以加一
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

时间复杂度:O(n);(遍历二叉树)

空间复杂度:O(1);(无使用额外空间)

迭代法

套用层序遍历的模板,只不过不加入节点值,直接计算节点数量

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        int result = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();//当层元素个数
            while (size -- > 0) {
                TreeNode cur = queue.poll();
                result++;//遍历一个元素则加1

                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
        }
        return result;
    }
}

时间复杂度:O(n);(遍历二叉树)

空间复杂度:O(n);(使用队列)

以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网

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

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

相关文章

基于SWOT的智能手机企业财务战略研究1.62

摘 要 近些年&#xff0c;网络技术日新月异&#xff0c;智能手机深受消费者喜爱&#xff0c;人们通过网络&#xff0c;手机应用&#xff0c;可以极大地方便人们学习&#xff0c;工作等等。由于国家对电信行业的大力支持&#xff0c;中国消费者群体逐步成为最具潜力的手机购买者…

基于单片机的IC 卡门禁系统设计

摘要:针对传统门锁钥匙易丢失、配置不便和忘记携带等问题,提出了一种基于STC89C52 的IC 卡门禁系统设计。该系统以STC89C52 单片机为核心来控制电子锁模块的开关。主要过程是由RFID 模块读取IC卡ID 并通过串口发送至STC89C52 单片机模块,STC89C52 单片机模块可以实现在线对I…

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的吸烟检测系统(深度学习+Python代码+PySide6界面+训练数据集)

摘要&#xff1a;本文详细说明了如何利用深度学习开发一个用于监测吸烟行为的系统&#xff0c;并分享了完整的代码实现。该系统采用了先进的YOLOv8算法&#xff0c;同时还使用YOLOv7、YOLOv6、YOLOv5算法&#xff0c;并对它们进行了性能比较&#xff0c;呈现了不同模型的性能指…

VS中配置生成事件

一、为什么需要使用生成事件&#xff1f; 在实际开发过程中&#xff0c;在项目生成DLL后&#xff0c;需要被复制到不同的目录下被引用&#xff0c;很麻烦。 我们可以利用VS中的项目生成事件属性来进行生成后的DLL复制到指定的目录&#xff0c;或者进去其他的操作&#xff0c;比…

C/C++——Tchisla求解器(多线程高性能版本)

前言 之前一篇文章中介绍的使用Python写的Tchisla求解器Python——Tchisla求解器&#xff08;暴力搜索法&#xff09;在我实际使用中有比较大的缺陷&#xff0c;首先是太慢了&#xff0c;对于每日一题中四位数的目标数字&#xff0c;往往搜索数个小时都找不完1~9的全部最优解&…

重学SpringBoot3-ErrorMvcAutoConfiguration类

更多SpringBoot3内容请关注我的专栏&#xff1a;《SpringBoot3》 期待您的点赞&#x1f44d;收藏⭐评论✍ 重学SpringBoot3-ErrorMvcAutoConfiguration类 ErrorMvcAutoConfiguration类的作用工作原理定制 ErrorMvcAutoConfiguration示例代码1. 添加自定义错误页面2.自定义错误控…

【小白学机器学习8】统计里的自由度DF=degree of freedom, 以及关于df=n-k, df=n-k-1, df=n-1 等自由度公式

目录 1 自由度 /degree of freedom / df 1.1 物理学的自由度 1.2 数学里的自由度 1.2.1 数学里的自由度 1.2.2 用线性代数来理解自由度&#xff08;需要补充&#xff09; 1.2.3 统计里的自由度 1.3 统计学里自由度的定义 2 不同对象的自由度 2.1 纯公式的自由度&#…

汤唯N次被封后,除了人美外,这些也许你没想到!

汤唯N次被封后&#xff0c;除了人美外&#xff0c;这些也许你没想到&#xff01; 引言&#xff1a;影坛的璀璨明星 #李秘书讲写作#注意到&#xff0c;在光鲜亮丽的电影圈&#xff0c;有一位女演员以其独特的气质和深入人心的演技&#xff0c;成为了众多观众心中的璀璨明星。她…

國内linux服务器解决Ollama安装超时

curl -fsSL https://ollama.com/install.sh | sh 执行一直超时 做如下配置&#xff1a; 修改hosts文件&#xff0c;直接将http://github.com做个ip指向。 sudo vim /etc/hosts 输入密码后&#xff0c;按 i 增加以下配置 # github 注意下面的IP地址和域名之间有一个空格 140…

朱熹凭着理学成为天选之子,读书方法也很实用

唐朝是李姓的天下&#xff0c;推行老子的道家思想。同时&#xff0c;佛教兴旺鼎盛。儒家开始没落&#xff0c;失去主要地位。为了恢复儒家的地位&#xff0c;朱憙极力发展理学。 理学又叫道学。北有孔子&#xff0c;南有朱子。朱憙是理学集大成者&#xff0c;被称为朱子。理学…

STM32的GPIO初始化配置-学习笔记

简介&#xff1a; 由于刚开始没有学懂GPIO的配置原理&#xff0c;导致后面学习其它外设的时候总是产生阻碍&#xff0c;因为其它外设要使用前&#xff0c;大部分都要配置GPIO的初始化&#xff0c;因此这几天重新学习了一遍GPIO的配置&#xff0c;记录如下。 首先我们要知道芯片…

基于支持向量机SVM的点火电流预测

目录 支持向量机SVM的详细原理 SVM的定义 SVM理论 Libsvm工具箱详解 简介 参数说明 易错及常见问题 完整代码和数据下载链接:基于支持向量机SVM的点火电流预测(代码完整,数据齐全)资源-CSDN文库 https://download.csdn.net/download/abc991835105/88947558 SVM应用实例,基…

.Net Core 中间件验签

文章目录 为什么是用中间件而不是筛选器&#xff1f;代码实现技术要点context.Request.EnableBuffering()指针问题 小结 为什么是用中间件而不是筛选器&#xff1f; 为什么要用中间件验签&#xff0c;而不是筛选器去验签? 1、根据上图我们可以看到&#xff0c;中间件在筛选器之…

【Rockchip android7.1 平台rtl8821cs wifi移植调试】

Rockchip 平台rtl8821cs wifi移植调试 问题描述解决方法 郑重声明:本人原创博文&#xff0c;都是实战&#xff0c;均经过实际项目验证出货的 转载请标明出处:攻城狮2015 Platform: Rockchip rk3128 OS:Android 7.1.2 Kernel: 3.10 问题描述 客户需要在现在的板子上调一款RTL882…

前端的数据标记协议

文章目录 数据标记协议是什么数据标记协议的作用常见的数据标记协议Open Graph protocol 开放图谱协议基本元数据协议可选元数据结构化属性 —— 元数据的属性多个相同的元数据标签类型元数据的使用方法全局类型使用自定义类型使用对象类型使用歌曲对象类型视频对象类型文章对象…

算法打卡day15|二叉树篇04|110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和

算法题 Leetcode 110.平衡二叉树 题目链接:110.平衡二叉树 大佬视频讲解&#xff1a;平衡二叉树视频讲解 个人思路 可以用递归法&#xff0c;计算左右子树的高度差&#xff0c;当超过1时就不为平衡二叉树了&#xff1b; 解法 回顾一下二叉树节点的深度与高度&#xff1b; …

软件测试知识面试题:白盒测试、黑盒测试、测试用例

文章目录 白盒测试1、白盒测试分两类2、白盒测试的四个原则3、白盒测试常用的7类测试 黑盒测试1、黑盒测试的优缺点2、黑盒测试的方法3、黑盒测试的原则 测试用例1、测试用例包含2、设计测试用例所需的文档资料3、采用白盒测试技术设计用例的目的4、采用黑盒测试技术设计用例的…

网络编程套接字(3)——Java数据报套接字(UDP协议)

目录 一、Java数据报套接字通信模型 二、UDP数据报套接字编程 1、DatagramSocket &#xff08;1&#xff09;DatagramSocket构造方法 &#xff08;2&#xff09;DatagramSocket方法 2、DatagramPacket &#xff08;1&#xff09;DatagramPacket构造方法 &#xff08;2&…

spring启动时如何自定义日志实现

一、现象 最近在编写传统的springmvc项目时&#xff0c;遇到了一个问题&#xff1a;虽然在项目的web.xml中指定了log4j的日志启动监听器Log4jServletContextListener&#xff0c;且开启了日志写入文件&#xff0c;但是日志文件中只记录业务代码中我们声明了日志记录器的日志&a…

HTML静态网页成品作业(HTML+CSS)——电影加勒比海盗介绍设计制作(1个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;未使用Javacsript代码&#xff0c;共有1个页面。 二、作品演示 三、代…