LeetCode 104. 二叉树的最大深度

104. 二叉树的最大深度

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

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

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:3

示例 2:

输入:root = [1,null,2]
输出:2

提示:

  • 树中节点的数量在 [0, 10^4] 区间内。
  • -100 <= Node.val <= 100

解法思路:

1、递归/深度优先遍历(Recursion,Depth-First Traversal)

2、迭代/广度优先遍历(Iterator,Breadth-First Traversal)

法一:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        // Recursion,Depth-First Traversal
        // Time: O(n) n 节点数
        // Space: O(h) h 高度
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

法二:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
       // Iterator, Breadth-First Traversal
        // Time: O(n) n 节点数
        // Space: O(n) 每一层最大的节点数,最好n,最坏1
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode node = queue.removeFirst();
                if (node.left != null) {
                    queue.addLast(node.left);
                }
                if (node.right != null) {
                    queue.addLast(node.right);
                }
            }
            depth++;
        }
        return depth;
    }
}

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

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

相关文章

Comdlg32.dll文件丢失怎么?Comdlg32.dll修复方法

很用人在打开软件或游戏的时候&#xff0c;电脑会弹出对话框“程序无法运行&#xff0c;因为Comdlg32.dll文件找不到&#xff0c;请尝试重新安装程序已解决问题”&#xff0c;这是怎么回事呢&#xff1f; 首先&#xff0c;我们先来了解“Comdlg32.dll文件”是什么&#xff1f; …

配置zabbix监控平台

目录 内容纯手敲&#xff0c;难免有误&#xff0c;若发现请私信我。 配置zabbix监控平台 一、进入官网 ​编辑​ 二、配置zabbix-server&#xff08;服务端&#xff09; 1.下载zabbix的yum源 2.安装Zabbix服务器、前端、代理 3.安装Zabbix前端 4.编辑文件/etc/yum.rep…

【vue】ant-col多列栅格式的表单排列方式布局异常:

文章目录 一、效果&#xff1a;二、解决&#xff1a;三、问题&#xff1a; 一、效果&#xff1a; 二、解决&#xff1a; 在row中添加布局类型&#xff1a;type“flex” 三、问题&#xff1a; 后期正式环境还是存在该问题 >>>.ant-form-item {max-height: 32px; }多…

【MATLAB基础绘图第19棒】绘制小提琴图

MATLAB绘制小提琴图 小提琴图&#xff08;Violin Plot&#xff09;案例1&#xff1a;基础绘制参考 小提琴图&#xff08;Violin Plot&#xff09; 小提琴图&#xff08;Violin Plot&#xff09;可用于展示多组数据的分布状态和概率密度。 出自论文-J2020-Drought hazard trans…

关系运算符

Oracle从入门到总裁:https://blog.csdn.net/weixin_67859959/article/details/135209645 补充: 如果要想对所选择的数据行进行控制&#xff0c;那么可以利用 WHERE 子句完成&#xff0c;此时的 SQL 语法结构变为如下形式 先系统性介绍下: ● 关系运算&#xff1a; >、、&…

Mysql深度分页优化的一个实践

问题简述: 最近在工作中遇到了大数据量的查询场景, 日产100w左右明细, 会查询近90天内的数据, 总数据量约1亿, 业务要求支持分页查询与导出. 无论是分页或导出都涉及到深度分页查询, mysql通过limit/offset实现的深度分页查询会存在全表扫描的问题, 比如offset1000w, limit10…

Baumer工业相机堡盟工业相机如何通过NEOAPI SDK使用相机日志跟踪功能(C++)

Baumer工业相机堡盟工业相机如何通过NEOAPI SDK使用相机日志跟踪功能&#xff08;C&#xff09; Baumer工业相机Baumer工业相机NEOAPI SDK和短曝光功能的技术背景Baumer工业相机通过NEOAPI SDK使用相机日志跟踪功能1.引用合适的类文件2.通过NEOAPI SDK使用相机日志跟踪功能3.通…

力扣每日一练(24-1-15)

重复n次检查&#xff0c;几乎都用双指针。。。 固然双指针就是题解&#xff1a; if len(nums) < 3:return len(nums)p1 2 for p2 in range(2, len(nums)):if nums[p2] ! nums[p1 - 2]:nums[p1] nums[p2]p1 1return p1 可以重复两次&#xff0c;那么隔一个检查就行&#…

避免问卷填写重复的方法:确保数据准确性的关键

如果我们收集的问卷显示很多相同的IP地址怎么办&#xff1f; 先不要着急。首先&#xff0c;先把这些来自相同IP地址的问卷整理出来&#xff0c;查看他们的数据是否一致。如果数据一致&#xff0c;并且数量较大的话&#xff0c;那么他们可能会对问卷结果造成一定的影响。我们需要…

Verilog语法——4.Verilog工程模板、相应规范再强调

参考资料 【明德扬_verilog零基础入门语法HDL仿真快速掌握-手把手教你写FPGA/ASIC代码设计流程中的应用】 4. Verilog工程模板、相应规范 4.1 Verilog工程模板 4.1.1 设计模块模板 module module_name(clk,rst_n,//其他信号&#xff0c;举例doutdout };//参数定义parameter …

渗透测试-靶机DC-2-知识点总结

靶机DC-2-知识点总结 一、前言二、实验环境三、渗透测试工具1. cewl&#xff08;1&#xff09;cewl简介&#xff08;2&#xff09;cewl常见用法 2. wpscan&#xff08;1&#xff09;wpscan简介&#xff08;2&#xff09;wpscan常见用法<1>直接扫描<2>-e u爆破用户名…

RabbitMQ交换机(3)-Topic

1.Topic模式 RabbitMQ的Topic模式是一种基于主题的消息传递模式。它允许发送者向一个特定的主题&#xff08;topic&#xff09;发布消息&#xff0c;同时&#xff0c;订阅者也可以针对自己感兴趣的主题进行订阅。 在Topic模式中&#xff0c; 主题通过一个由单词和点号组成的字…

如何在苹果手机上进行文件管理

摘要 苹果手机没有像安卓系统那样内置文件管理器&#xff0c;但是可以通过使用克魔开发助手来实现强大的文件管理功能。本文介绍了如何使用克魔开发助手在电脑上管理和传输苹果手机的文件。 引言 很多朋友都在使用苹果手机&#xff0c;但是当需要查看手机中的文件时&#xf…

STM32开发板,Win10、Win11 上的驱动安装说明

一、USB线插到 CMSIS-DAP 接口上&#xff0c;将自动识别到两个设备 ① CMSIS-DAP&#xff1a;用于烧录代码、在线硬件仿真; 在Keil里烧录&#xff0c;无需通过FlyMCU; ② USB转TTL&#xff1a;用于开发板与电脑间串口通信 &#xff0c;即USART1, TX-PA9、RX-PA10; 接口备注&a…

如何实现无公网ip远程访问内网本地BUG管理服务【内网穿透】

文章目录 前言1. 本地安装配置BUG管理系统2. 内网穿透2.1 安装cpolar内网穿透2.2 创建隧道映射本地服务3. 测试公网远程访问4. 配置固定二级子域名4.1 保留一个二级子域名5.1 配置二级子域名6. 使用固定二级子域名远程 前言 BUG管理软件,作为软件测试工程师的必备工具之一。在…

2023年山东省职业院校技能大赛高职组信息安全管理与评估 模块二(正式赛)

2023年山东省职业院校技能大赛高职组信息安全管理与评估 模块二 模块二竞赛项目试题 根据信息安全管理与评估技术文件要求&#xff0c;模块二为网络安全事件响应、数字取证调查和 应用程序安全。本文件为信息安全管理与评估项目竞赛-模块二试题。 介绍 竞赛有固定的开始和结…

使用 Categraf 采集 Nginx 指标

1. 前言 工作中需要监控 Nginx 的指标&#xff0c;选用的指标采集器是 Categraf&#xff0c;特此记录下&#xff0c;以备后用。 此文档并未详细记录详细的操作细节&#xff0c;只记录了大概的操作步骤&#xff0c;仅供参考。 2. 采集基础指标 2.1. 暴露 Nginx 自带的指标采…

【数据结构】哈希表详解,举例说明 java中的 HashMap、HashTable及其区别

一、哈希表&#xff08;Hash Table&#xff09;简介&#xff1a; 哈希表是一种数据结构&#xff0c;用于实现字典或映射等抽象数据类型。它通过把关键字映射到表中的一个位置来实现快速的数据检索。哈希表的基本思想是利用哈希函数将关键字映射到数组的索引位置上&#xff0c;…

EDA-数据探索-pandas自带可视化-iris

# 加载yellowbrick数据集 import os import pandas as pd FIXTURES os.path.join(os.getcwd(), "data") df pd.read_csv(os.path.join(FIXTURES,"iris.csv")) df.head()sepal_lengthsepal_widthpetal_lengthpetal_widthspecies05.13.51.40.2setosa14.93…

二.几何基础_直线

O以下皆为公理推导的定理,有公理组成的新的定义 一.角 1.由线所组成的新的定义 角: 一点出发由两个不同方向的射线组成的图像(注:构成角的边是无界线的) 顶点: 两射线交汇处,如图 可称顶点为 ∠ A 或 ∠ C A B , ∠ B A C ∠A或∠CAB,∠BAC ∠A或∠CAB,∠BAC边: 构成角的射…