多叉树题目:N 叉树的最大深度

2024-04-02 08:28
文章标签 题目 深度 最大 多叉树

本文主要是介绍多叉树题目:N 叉树的最大深度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法一
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法二
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:N 叉树的最大深度

出处:559. N 叉树的最大深度

难度

3 级

题目描述

要求

给定一个 N 叉树,返回其最大深度。

最大深度是从根结点到最远叶结点的最长路径上的结点数。

N 叉树在输入中按层序遍历序列化表示,每组子结点由空值 null \texttt{null} null 分隔(请参见示例)。

示例

示例 1:

示例 1

输入: root = [1,null,3,2,4,null,5,6] \texttt{root = [1,null,3,2,4,null,5,6]} root = [1,null,3,2,4,null,5,6]
输出: 3 \texttt{3} 3

示例 2:

示例 2

输入: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] \texttt{root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]} root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出: 5 \texttt{5} 5

数据范围

  • 树中结点数目在范围 [0, 10 4 ] \texttt{[0, 10}^\texttt{4}\texttt{]} [0, 104]
  • N 叉树的高度小于或等于 1000 \texttt{1000} 1000

解法一

思路和算法

如果 N 叉树为空,则深度为 0 0 0。对于非空 N 叉树,首先计算每个子树的最大深度,子树最大深度的最大值加 1 1 1 即为 N 叉树的最大深度,每个子树的最大深度可以使用同样的方式计算。因此可以使用深度优先搜索计算 N 叉树的最大深度。

计算 N 叉树的最大深度的过程是一个递归的过程,递归的终止条件是 N 叉树为空,此时 N 叉树的最大深度为 0 0 0。对于非空 N 叉树,首先递归地计算每个子树的最大深度,然后将子树最大深度的最大值加 1 1 1 即为 N 叉树的最大深度。

代码

class Solution {public int maxDepth(Node root) {if (root == null) {return 0;}int childDepth = 0;List<Node> children = root.children;for (Node child : children) {childDepth = Math.max(childDepth, maxDepth(child));}return childDepth + 1;}
}

复杂度分析

  • 时间复杂度: O ( m ) O(m) O(m),其中 m m m 是 N 叉树的结点数。每个结点都被访问一次。

  • 空间复杂度: O ( m ) O(m) O(m),其中 m m m 是 N 叉树的结点数。空间复杂度主要是递归调用的栈空间,取决于 N 叉树的高度,最坏情况下 N 叉树的高度是 O ( m ) O(m) O(m)

解法二

思路和算法

也可以使用广度优先搜索计算 N 叉树的最大深度。

广度优先搜索需要使用队列存储待访问的结点,初始时将根结点入队列。最简单的广度优先搜索的做法是,每次将一个结点出队列,然后将该结点的子结点入队列,直到队列为空时遍历结束。

这道题需要计算 N 叉树的最大高度,因此在广度优先搜索的过程中需要维护深度的信息,实现和最简单的广度优先搜索有所不同。为了维护深度信息,需要确保每一轮访问的结点为同一层的全部结点。

初始时,队列内只有根结点,是同一层的全部结点。每一轮访问结点之前需要首先得到队列内的元素个数,此时队列内的元素为同一层的全部结点,然后访问这些结点,并将这些结点的子结点入队列。一轮访问结束之后,当前层的全部结点都已经出队列并被访问,此时队列内的元素为下一层的全部结点,下一轮访问时即可访问下一层的全部结点。使用上述做法,可以确保每一轮访问的结点为同一层的全部结点。

在确保每一轮访问的结点为同一层的全部结点的情况之下,根据访问的总轮数即可得到 N 叉树的最大深度,其中根结点的深度为 1 1 1

代码

class Solution {public int maxDepth(Node root) {if (root == null) {return 0;}int depth = 0;Queue<Node> queue = new ArrayDeque<Node>();queue.offer(root);while (!queue.isEmpty()) {depth++;int size = queue.size();for (int i = 0; i < size; i++) {Node node = queue.poll();List<Node> children = node.children;for (Node child : children) {queue.offer(child);}}}return depth;}
}

复杂度分析

  • 时间复杂度: O ( m ) O(m) O(m),其中 m m m 是 N 叉树的结点数。每个结点都被访问一次。

  • 空间复杂度: O ( m ) O(m) O(m),其中 m m m 是 N 叉树的结点数。空间复杂度主要是队列空间,队列内元素个数不超过 n n n

这篇关于多叉树题目:N 叉树的最大深度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

深度解析Java DTO(最新推荐)

《深度解析JavaDTO(最新推荐)》DTO(DataTransferObject)是一种用于在不同层(如Controller层、Service层)之间传输数据的对象设计模式,其核心目的是封装数据,... 目录一、什么是DTO?DTO的核心特点:二、为什么需要DTO?(对比Entity)三、实际应用场景解析

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧

深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

《深度解析SpringBoot拦截器Interceptor与过滤器Filter的区别与实战指南》本文深度解析SpringBoot中拦截器与过滤器的区别,涵盖执行顺序、依赖关系、异常处理等核心差异,并... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

SpringBoot开发中十大常见陷阱深度解析与避坑指南

《SpringBoot开发中十大常见陷阱深度解析与避坑指南》在SpringBoot的开发过程中,即使是经验丰富的开发者也难免会遇到各种棘手的问题,本文将针对SpringBoot开发中十大常见的“坑... 目录引言一、配置总出错?是不是同时用了.properties和.yml?二、换个位置配置就失效?搞清楚加

Python中文件读取操作漏洞深度解析与防护指南

《Python中文件读取操作漏洞深度解析与防护指南》在Web应用开发中,文件操作是最基础也最危险的功能之一,这篇文章将全面剖析Python环境中常见的文件读取漏洞类型,成因及防护方案,感兴趣的小伙伴可... 目录引言一、静态资源处理中的路径穿越漏洞1.1 典型漏洞场景1.2 os.path.join()的陷

Spring Boot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)

《SpringBoot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)》:本文主要介绍SpringBoot拦截器Interceptor与过滤器Filter深度解析... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现与实

MyBatis分页插件PageHelper深度解析与实践指南

《MyBatis分页插件PageHelper深度解析与实践指南》在数据库操作中,分页查询是最常见的需求之一,传统的分页方式通常有两种内存分页和SQL分页,MyBatis作为优秀的ORM框架,本身并未提... 目录1. 为什么需要分页插件?2. PageHelper简介3. PageHelper集成与配置3.

Maven 插件配置分层架构深度解析

《Maven插件配置分层架构深度解析》:本文主要介绍Maven插件配置分层架构深度解析,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Maven 插件配置分层架构深度解析引言:当构建逻辑遇上复杂配置第一章 Maven插件配置的三重境界1.1 插件配置的拓扑