当前位置: 首页 > news >正文

Java——二叉树的深度

题目链接

牛客网在线oj题——二叉树的深度

题目描述

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度,根节点的深度视为 1 。

数据范围:节点的数量满足 0≤n≤100 ,节点上的值满足0≤val≤100

进阶:空间复杂度 O(1) ,时间复杂度 O(n)

假如输入的用例为{1,2,3,4,5,#,6,#,#,7},那么如下图:
在这里插入图片描述

题目示例

示例1

输入:
{1,2,3,4,5,#,6,#,#,7}

返回值:
4

示例2

输入:
{}

返回值:
0

解题思路一

使用广度优先搜索,将二叉树进行层序遍历,每遍历一层就将depth++

广度优先遍历需要借助队列,首先将根节点加入到queue中,然后每次先确定队列的大小size,然后弹出size个元素,分别将这些元素的左子树和右子树加入到队列中(如果不为null)

上面每次弹出size个元素的过程就是遍历一层的过程,因此此时将depth++即可

例如:
在这里插入图片描述
首先将根节点加入队列中,depth++
在这里插入图片描述

现在queue的长度是1,弹出1个元素,将其左子树和右子树添加进队列,depth++
在这里插入图片描述
现在queue的长度是2,弹出2个元素,将其左子树和右子树添加进队列,depth++
在这里插入图片描述
现在queue的长度是3,弹出3个元素,将其左子树和右子树添加进队列,depth++
在这里插入图片描述

现在queue的长度是1,弹出1个元素,此时该元素左子树和右子树都为null,不再向队列中添加元素,循环结束,depth = 4

方法一完整代码

import java.util.*;
/**
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/
public class Solution {public int TreeDepth(TreeNode root) {if(root == null){return 0;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);int depth = 0;while(!queue.isEmpty()) {int size = queue.size();depth++;for (int i = 0; i < size; i++) {TreeNode cur = queue.poll();if (cur.left != null) {queue.add(cur.left);}if(cur.right != null){queue.add(cur.right);}}}return depth;}
}

思路二

深度优先搜索,分别确定左右子树中深度的较大值

使用递归分别确定节点的左子树高度和右子树高度,每次递归到下一层节点都需要将depth + 1,如果此时depth的长度大于max,就将max的值更新为depth,这样就可以返回左右子树高度的较大者

方法二完整代码

/**
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}
*/
public class Solution {public int TreeDepth(TreeNode root) {if(root == null){return 0;}int depth = 0;int[] max = new int[1];max[0] = 0;TreeDepthHelper(root, depth, max);return max[0];}private void TreeDepthHelper(TreeNode root, int depth, int[] max) {if(root == null){if(max[0] < depth){max[0] = depth;}return;}TreeDepthHelper(root.left, depth + 1, max);TreeDepthHelper(root.right, depth + 1, max); }
}

思路三

和思路二类似,形式上更容易理解

我们认为最下面的空指针null为第0层,往上走每层加一

因此,我们只需要统计左子树的高度和右子树高度中的较大值,然后再加1即可得到当前节点的高度

方法三完整代码

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

相关文章:

Java——二叉树的深度

题目链接 牛客网在线oj题——二叉树的深度 题目描述 输入一棵二叉树&#xff0c;求该树的深度。从根结点到叶结点依次经过的结点&#xff08;含根、叶结点&#xff09;形成树的一条路径&#xff0c;最长路径的长度为树的深度&#xff0c;根节点的深度视为 1 。 数据范围&am…...

一般现在时(二)

一般现在时(二) 1.什么叫实义动词? 实义动词是指表示有具体意思的动词&#xff0c;也叫行为动词。 例如:like(喜欢) eat(吃) live(居住) have(有) run(跑)等等。 实义动词占英语中动词的绝大多数 &#x1f516;我们已学过的be动词可译为是,有时译为成为,有时则没有具体意…...

leetcode657. 机器人能否返回原点

题目描述解题思路执行结果 leetcode657. 机器人能否返回原点 题目描述 机器人能否返回原点 在二维平面上&#xff0c;有一个机器人从原点 (0, 0) 开始。给出它的移动顺序&#xff0c;判断这个机器人在完成移动后是否在 (0, 0) 处结束。 移动顺序由字符串 moves 表示。字符 mov…...

DAY 48 Nginx的 location与rewrite模块

[正则表达式] 常用的[Nginx] 正则表达式 $ &#xff1a;匹配输入字符串的结束位置* &#xff1a;匹配前面的字符零次或多次。如“ol*”能匹配“o”及“ol”、“oll” &#xff1a;匹配前面的字符一次或多次。如“ol”能匹配“ol”及“oll”、“olll”&#xff0c;但不能匹配“…...

Linux 常用操作技巧

Linux 操作技巧大全 Linux是一种强大的操作系统&#xff0c;掌握各种操作技巧可以帮助我们惬意地使用它。在这篇博客中&#xff0c;我们将分享一些实用的Linux技巧&#xff0c;希望能对您有所帮助&#xff01; 1. 使用Tab进行自动补全 在输入命令时&#xff0c;按下Tab键可…...

BetaFlight统一硬件配置文件研读之timer命令

BetaFlight统一硬件配置文件研读之timer命令 1. 源由2. 代码分析3. 实例分析4. 配置情况4.1 AFn配置查表4.2 timer4.3 timer show4.4 timer pin list 5. 参考资料 统一硬件配置文件的设计是一种非常好的设计模式&#xff0c;可以将硬件和软件的工作进行解耦。 1. 源由 cli命令…...

码出高效:Java开发手册笔记(java对象四种引用关系及ThreadLocal)

码出高效&#xff1a;Java开发手册笔记&#xff08;java对象四种引用关系及ThreadLocal&#xff09; 前言一、引用类型二、ThreadLocal价值三、ThreadLocal副作用 前言 “水能载舟&#xff0c;亦能覆舟。”用这句话来形容 ThreadLocal 最贴切不过。ThreadLocal 初衷是在线程并…...

为什么要进行数据决策?数据决策对企业而言有何重要意义?

“大数据”几乎已成为时下最时髦的词汇&#xff0c;不夸张地说&#xff0c;当今各行各业无不对大数据充满了向往&#xff0c;希望自己在新一轮的大数据营销中抢占先机。同时&#xff0c;从大数据中引申出的数据挖掘、数据分析、数据安全等数据运用技术也成为人们热捧的焦点。 …...

2. Java 异常体系

2.1 Throwable java.lang.Throwable 类是 Java 程序执行过程中发生的异常事件对应的类的根父类。 Throwable 中的常用方法&#xff1a; public void printStackTrace()&#xff1a;打印异常的详细信息。 包含了异常的类型、异常的原因、异常出现的位置、在开发和调试阶段都得…...

如何学好STM32,需要哪些步骤?

学习STM32应用于项目开发需要以下步骤&#xff1a; 学习STM32的基本知识&#xff1a;包括STM32的架构、寄存器、外设等&#xff0c;理解STM32的工作原理和基本操作方法。 学习嵌入式系统和RTOS的基础知识&#xff1a;了解嵌入式系统的概念、RTOS的基本原理和使用方法&#xff…...

武忠祥老师每日一题||不定积分基础训练(四)

∫ d x 1 x 3 \int \frac{\rm dx}{1x^3} ∫1x3dx​ 解法一&#xff1a; 待定系数法&#xff1a; ∫ d x 1 x 3 \int \frac{dx}{1x^3} ∫1x3dx​ ∫ d x ( 1 x ) ( x 2 − x 1 ) \int \frac{dx}{(1x)(x^2-x1)} ∫(1x)(x2−x1)dx​ 1 3 ∫ ( 1 x 1 − x 2 x 2 − x …...

记一次产线打印json导致的redis连接超时

服务在中午十一点上线后&#xff0c;服务每分钟发出三到四次redis连接超时告警。错误信息为&#xff1a; Dial err:dial tcp: lookup xxxxx: i/o timeout 排查过程 先是检查redis机器的情况&#xff0c;redis写入并发数较大&#xff0c;缓存中保留了一小时大概400w条数据。red…...

FPGA入门系列12--RAM的使用

文章简介 本系列文章主要针对FPGA初学者编写&#xff0c;包括FPGA的模块书写、基础语法、状态机、RAM、UART、SPI、VGA、以及功能验证等。将每一个知识点作为一个章节进行讲解&#xff0c;旨在更快速的提升初学者在FPGA开发方面的能力&#xff0c;每一个章节中都有针对性的代码…...

【三十天精通Vue 3】第二十六天 Vue3 与 TypeScript 最佳实践

✅创作者&#xff1a;陈书予 &#x1f389;个人主页&#xff1a;陈书予的个人主页 &#x1f341;陈书予的个人社区&#xff0c;欢迎你的加入: 陈书予的社区 &#x1f31f;专栏地址: 三十天精通 Vue 3 文章目录 引言一、为什么使用TypeScript&#xff1f;二、Vue 3和TypeScript…...

ffmpeg-mov-metadate不识别Bug修复

文章目录 BUG起因类似问题反馈问题解决具体步骤&#xff1a; 阅读过文章ffmpeg命令行解析调试流程记录movenc.c源码分析 BUG起因 在ffmpeg参数默认可识别的metadata参数如下&#xff1a; 具体可见libavformat/movenc.c->mov_write_udta_tag() mov_write_string_metadata(s,…...

(8)(8.6) 引导程序更新

文章目录 前言 1 我在哪里可以下载最新的引导程序? 2 使用任务规划器进行升级...

汽车电路图、原理框图、线束图、元器件布置图的识读技巧与要点

摘要&#xff1a; 想要读懂汽车电路图就必须把电的通路理清楚&#xff0c;即某条线是什么信号&#xff0c;该信号是输入信号、输出信号还是控制信号以及信号起什么作用&#xff0c;在什么条件下有信号&#xff0c;从哪里来&#xff0c;到哪里去。 一、汽车电路图的识读技巧 1.…...

( 数组和矩阵) 667. 优美的排列 II ——【Leetcode每日一题】

❓667. 优美的排列 II 难度&#xff1a;中等 给你两个整数 n 和 k &#xff0c;请你构造一个答案列表 answer &#xff0c;该列表应当包含从 1 到 n 的 n 个不同正整数&#xff0c;并同时满足下述条件&#xff1a; 假设该列表是 answer [a1, a2, a3, ... , an] &#xff0…...

【python基础语法七】python内置函数和内置模块

内置全局函数 abs 绝对值函数 print(abs(-1)) # 1 print(abs(100)) # 100round 四舍五入 """奇进偶不进(n.5的情况特定发生)""" res round(3.87) # 4 res round(4.51) # 5 # res round(2.5) # 2 # res round(3.5) # 4 res round(6.5) # …...

81. read readline readlines 读取文件的三种方法

81. read readline readlines 读取文件的三种方法 文章目录 81. read readline readlines 读取文件的三种方法1. 读取文件的三种方法2. read方法3. readline方法4. readlines方法5. 代码总结5.1 read方法读取全部内容5.2 readline方法读取一行&#xff0c;返回字符串5.3 readli…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...