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

本文主要是介绍算法打卡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);(递归树的高度h)


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(n);(递归树的高度h

迭代法

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

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 ++;//根节点深度加1int 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;}// 左右结点都不为nullreturn Math.min(leftDepth, rightDepth) + 1;}
}

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

空间复杂度:O(n);(递归树的高度h)


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(n);(递归树的高度h)

迭代法

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

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++;//遍历一个元素则加1if (cur.left != null) queue.offer(cur.left);if (cur.right != null) queue.offer(cur.right);}}return result;}
}

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

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

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

这篇关于算法打卡day14|二叉树篇03|104.二叉树的最大深度、559.n叉树的最大深度、111.二叉树的最小深度、222.完全二叉树的节点个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/810342

相关文章

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

Linux find 命令完全指南及核心用法

《Linuxfind命令完全指南及核心用法》find是Linux系统最强大的文件搜索工具,支持嵌套遍历、条件筛选、执行动作,下面给大家介绍Linuxfind命令完全指南,感兴趣的朋友一起看看吧... 目录一、基础搜索模式1. 按文件名搜索(精确/模糊匹配)2. 排除指定目录/文件二、根据文件类型筛选三、时间

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》:本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR