【力扣】104. 二叉树的最大深度、111. 二叉树的最小深度

104. 二叉树的最大深度

题目描述

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

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

示例 1:
在这里插入图片描述

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

示例 2:

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

提示:

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

解题方法

  • C 深度优先搜索——递归
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int my_max(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

int maxDepth(struct TreeNode* root) {
    if (NULL == root) {
        return 0;
    }
    int left = maxDepth(root->left);
    int right = maxDepth(root->right);
    return my_max(left, right) + 1;
}

复杂度分析
时间复杂度:O(n),其中 n 为二叉树节点的个数。
空间复杂度:O(h),其中 h表示二叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于二叉树的高度。


111. 二叉树的最小深度

题目描述

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

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

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

示例 1:
在这里插入图片描述

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

示例 2:

输入:root = [2,null,3,null,4,null,5,null,6]
输出:5

提示:

  • 树中节点数的范围在 [0, 105] 内
  • -1000 <= Node.val <= 1000

解题方法

  • C 深度搜索——递归
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int my_min(int a, int b) {
    if (a > b)
        return b;
    else
        return a;
}

int minDepth(struct TreeNode* root) {
    if (NULL == root) {
        return 0;
    }
    if (NULL == root->left && NULL == root->right) {
        return 1;
    }

    int min_depth = INT_MAX;
    if (NULL != root->left) {
        min_depth = my_min(minDepth(root->left), min_depth);
    }

    if (NULL != root->right) {
        min_depth = my_min(minDepth(root->right), min_depth);
    }

    return min_depth + 1;
}

复杂度分析
时间复杂度:O(N),其中 N 是树的节点数。对每个节点访问一次。
空间复杂度:O(H),其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销,最坏情况下,树呈现链状,空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关,空间复杂度为 O(log⁡N)。

参考@力扣官方题解

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

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

相关文章

机器学习与自主系统

Darpa人工智能中有两个重要方向&#xff0c;一是机器学习&#xff0c;另一个就是自主系统。但真实博弈环境下&#xff0c;更重要的是人机融合体系… 机器学习是一种人工智能的分支&#xff0c;通过使用统计学和数学模型来让计算机系统学习和改进其性能。它可以让计算机从数据中…

FreeRTOS创建第一个程序

使用freeRTOS创建任务时使用如下函数 函数的参数 创建一个FreeRTOS任务点亮led灯实现led灯500毫秒翻转一次 具体的代码实现 #include "stm32f10x.h" // Device header #include "Delay.h" #include "freeRTOS.h" #include &quo…

【bash】linux使用环境变量拼接字符串错误

有如下脚本init-env.sh #!/bin/bash export HADOOP_HOME/opt/hadoop export HADOOP_CONF$HADOOP_HOME/conf执行结果&#xff1a; source init-env.sh echo $HADOOP_CONF_DIR # 得到结果&#xff1a;conf/hadoop&#xff0c;预期因该是/opt/hadoop/conf原因就是linux下使用了w…

零售EDI:Princess Auto EDI对接

Princess Auto 是一家加拿大零售连锁店&#xff0c;专门从事农场、工业、车库、液压和剩余物品的销售。 Princess Auto 总部位于马尼托巴省温尼伯&#xff0c;截至 2024 年 1 月在 10 个省份拥有并经营 55 家商店以及三个配送中心。各种商品均以其“Powerfist”和“Pro.Point”…

Qt 多窗体

前言 在 Qt编程中经常会遇到要在多个界面之间切换的情况&#xff0c;如从登录界面跳转到主界面&#xff0c;从主界面跳转到设置界面&#xff0c;再返回到主界面。我们将会用一个简单的示例来实现多窗体功能。 登录窗口 创建基类为QMainWindow&#xff0c;类名为LoginWin。再使用…

苹果开发者后台添加udid后,xcode中 Devices 数量没有更新问题

删除 文件夹 /Users/…/Library/MobileDevice/Provisioning Profiles 如何打开&#xff1a;https://zhuanlan.zhihu.com/p/563928113 回到Xcode刷新包名下面的警告验证&#xff08;可能需要翻墙&#xff09; 完毕&#xff01;

网站SEO关键词规划时如何筛选出合适的关键词?

在网站SEO优化过程中&#xff0c;关键词布局是一个至关重要的环节。首先&#xff0c;我们需要确定核心关键词&#xff0c;然后通过各种策略和方法对关键词进行扩展。完成关键词扩展后&#xff0c;接下来的任务就是对这些扩展后的关键词进行筛选。那么&#xff0c;如何进行有效的…

WordPress LayerSlider插件SQL注入漏洞复现(CVE-2024-2879)

0x01 产品简介 WordPress插件LayerSlider是一款可视化网页内容编辑器、图形设计软件和数字视觉效果应用程序,全球活跃安装量超过 1,000,000 次。 0x02 漏洞概述 WordPress LayerSlider插件版本7.9.11 – 7.10.0中,由于对用户提供的参数转义不充分以及缺少wpdb::prepare(),…

AI大模型之ChatGPT科普(深度好文)

目录 训练ChatGPT分几步&#xff1f; 如何炼成ChatGPT&#xff1f; 如何微调ChatGPT? 如何强化ChatGPT? 如何调教ChatGPT? AI思维链是什么&#xff1f; GPT背后的黑科技Transformer是什么&#xff1f; Transformer在计算机视觉上CV最佳作品&#xff1f; ChatGPT是人…

[leetcode]remove-duplicates-from-sorted-list

. - 力扣&#xff08;LeetCode&#xff09; 给定一个已排序的链表的头 head &#xff0c; 删除所有重复的元素&#xff0c;使每个元素只出现一次 。返回 已排序的链表 。 示例 1&#xff1a; 输入&#xff1a;head [1,1,2] 输出&#xff1a;[1,2]示例 2&#xff1a; 输入&…

LeetCode-热题100:148. 排序链表

题目描述 给你链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 示例 1&#xff1a; 输入&#xff1a; head [4,2,1,3] 输出&#xff1a; [1,2,3,4] 示例 2&#xff1a; 输入&#xff1a; head [-1,5,3,4,0] 输出&#xff1a; [-1,0,3,4,5] 示例…

2017NOIP普及组真题 4. 跳房子

线上OJ&#xff1a; 一本通&#xff1a;http://ybt.ssoier.cn:8088/problem_show.php?pid1417\ 核心思想 首先、本题中提到 “ 至少 要花多少金币改造机器人&#xff0c;能获得 至少 k分 ”。看到这样的话语&#xff0c;基本可以考虑要使用 二分答案。 那么&#xff0c;本题中…

Java快速入门系列-7(测试与调试)

第七章:测试与调试 第7章:测试与调试7.1 单元测试(JUnit)7.1.1 为什么要进行单元测试7.1.2 JUnit基础7.1.3 断言7.1.4 测试套件7.2 集成测试与系统测试7.2.1 集成测试7.2.2 系统测试7.3 调试技巧与工具7.3.1 断点7.3.2 单步执行7.3.3 变量检查7.3.4 条件断点7.3.5 日志记录…

手动实现简易版RPC(一)

手动实现简易版RPC(一) 前言 什么是RPC&#xff1f;它的原理是什么&#xff1f;它有什么特点&#xff1f;如果让你实现一个RPC框架&#xff0c;你会如何是实现&#xff1f;带着这些问题&#xff0c;开始今天的学习。 本文主要介绍RPC概述以及一些关于RPC的知识&#xff0c;为…

网络安全指南:安全访问 Facebook 的技巧

在当今数字化时代&#xff0c;网络安全问题越来越受到人们的关注。尤其是在社交媒体平台上&#xff0c;如 Facebook 这样的巨头&#xff0c;用户的个人信息和隐私更容易受到威胁。为了保护自己的在线安全&#xff0c;我们需要采取一些措施来确保在使用 Facebook 时能够安全可靠…

GET与POST:详述HTTP两大请求方法的语义、数据处理机制、安全特性与适用场景

GET和POST方法在HTTP请求中具有明确的角色分工和特性差异。GET适用于读取操作和不敏感数据的传递&#xff0c;强调可缓存性和安全性&#xff0c;而POST适用于写入操作和敏感数据的提交&#xff0c;提供了更大的数据承载能力和更强的隐私保护。本文详细介绍了GET与POST请求方法的…

利用Sentinel解决雪崩问题(二)隔离和降级

前言&#xff1a; 虽然限流可以尽量避免因高并发而引起的服务故障&#xff0c;但服务还会因为其它原因而故障。而要将这些故障控制在一定范围避免雪崩&#xff0c;就要靠线程隔离(舱壁模式)和熔断降级手段了&#xff0c;不管是线程隔离还是熔断降级&#xff0c;都是对客户端(调…

实战篇05:更新用户基本信息

实战篇05&#xff1a;更新用户基本信息 一、接口信息 1.1 基本信息 请求路径&#xff1a;/user/update 请求方式&#xff1a;PUT 接口描述&#xff1a;该接口用于更新已登录用户的基本信息(除头像和密码) 1.2 请求参数 请求参数格式&#xff1a;application/json 请求参数说…

2024 年 3 月公链行业研报:比特币创新高、Meme 掀热潮、AI 板块露头角

作者&#xff1a;stellafootprint.network 数据来源&#xff1a;Footprint Analytics 公链研究页面 3 月份&#xff0c;加密市场表现强劲&#xff0c;比特币再创历史新高。以太坊价格稳步攀升&#xff0c;而坎昆升级则显著降低了交易成本。Solana 链上 Meme 热潮席卷而来&am…

nandgame中的Memory(内存操作):栈、堆、静态区

Push Memory Push Memory 将内存中的值push到栈内堆栈顶部的值是一个内存地址。从堆栈中弹出地址。获取内存地址的当前内容&#xff0c;并将其推送到堆栈上。POP_A //堆栈顶部的值是一个内存地址。从堆栈中弹出地址。 D *A //获取内存地址的当前内容 PUSH_D //将其推送到…