Day16:LeedCode 104.二叉树的最大深度 111.二叉树最小深度 222.完全二叉树的结点个数

本文主要是介绍Day16:LeedCode 104.二叉树的最大深度 111.二叉树最小深度 222.完全二叉树的结点个数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

104. 二叉树的最大深度

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

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

思路:根结点最大深度=max(左子树最大深度,右子树最大深度)+1

终止条件,结点为null,该结点最大深度为0

class Solution {public int maxDepth(TreeNode root) {if(root==null)return 0;return Math.max(maxDepth(root.left),maxDepth(root.right))+1;}}

111. 二叉树的最小深度

给定一个二叉树,找出其最小深度。

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

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

本题跟上题类似,但有差别

错误代码:

 与上一题求最大深度比,区别在这

当左右结点都不为空时: length=1+Math.min(minDepth(root.left),minDepth(root.right))

当左节点为空时:length=minDepth(root.right)+1

当右结点为空时:length=minDepth(root.left)+1

当根节点为空时:length=0;

 

class Solution {public int minDepth(TreeNode root) {if(root==null)return 0;if(root.left==null){return minDepth(root.right)+1;} else if (root.right==null){return minDepth(root.left)+1;}else{return 1+Math.min(minDepth(root.left),minDepth(root.right));}}
}

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

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

思路:

求普通二叉树结点个数:
结点个数=左子树结点个数+右子树结点个数+1

class Solution {public int countNodes(TreeNode root) {if(root==null)return 0;return countNodes(root.left)+countNodes(root.right)+1;}
}

我们可以把完全二叉树当成普通二叉树来求结点个数,但上面方法没利用完全二叉树的特性

 

完全二叉树的两种情况:

1.完全二叉树为满二叉树,结点个数总数= 2^树深度 - 1

2.完全二叉树不为满二叉树,但是其左子树或者右子树为满二叉树 ,满二叉树可以直接用公式计算结点个数,对于非满二叉树结点总数=左子树结点总数+右结点总数+1

 

这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢?

在完全二叉树中,如果递归向左遍历的深度等于递归向右遍历的深度,那说明就是满二叉树。如图:

递归三部曲:

1.确定返回值和参数,返回结点个数int 传入结点root

2.确认结束条件:当该子树为满二叉树为直接计算该子树结点总数

                          当该子树为Null时,结点个数为0

3.递归逻辑:当前子树结点个数=1+ countNodes(root.left)+countNodes(root.right)

class Solution {public int countNodes(TreeNode root) {if(root==null)return 0;int left_length=0;TreeNode leftN=root.left;while(leftN!=null){leftN=leftN.left;left_length++;}int right_length=0;TreeNode rightN=root.right;while(rightN!=null){rightN=rightN.right;right_length++;}if(right_length==left_length){return (2 <<  right_length) - 1;}return 1+ countNodes(root.left)+countNodes(root.right);
}
}

 

 

 

 

 

 

 

 

 

 

这篇关于Day16:LeedCode 104.二叉树的最大深度 111.二叉树最小深度 222.完全二叉树的结点个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

深度解析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()的陷

Python使用Reflex构建现代Web应用的完全指南

《Python使用Reflex构建现代Web应用的完全指南》这篇文章为大家深入介绍了Reflex框架的设计理念,技术特性,项目结构,核心API,实际开发流程以及与其他框架的对比和部署建议,感兴趣的小伙... 目录什么是 ReFlex?为什么选择 Reflex?安装与环境配置构建你的第一个应用核心概念解析组件

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.