【LeetCode热题100】104. 二叉树的最大深度(二叉树)

一.题目要求

给定一个二叉树 root ,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

二.题目难度

简单

三.输入样例

示例 1:
在这里插入图片描述
输入:root = [3,9,20,null,null,15,7]
输出:3

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

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

四.解题思路

解法1:DFS后序遍历求深度
解法2:BFS层序遍历,从root开始将每层结点的左右孩子加入,处理完一层depth++,直到队列空。

五.代码实现

DFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        //后序遍历
        //左子树
        int left = maxDepth(root->left);
        //右子树
        int right = maxDepth(root->right);
        //求深度
        return left > right ? left + 1 : right + 1;
    }
};

BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> treeq;
        int depth = 0;
        treeq.push(root);
        while(!treeq.empty())
        {
            int remained = treeq.size();
            while(remained > 0)
            {
                TreeNode* tmp = treeq.front();
                treeq.pop();
                remained--;
                if (tmp->left != nullptr) treeq.push(tmp->left);
                if (tmp->right != nullptr) treeq.push(tmp->right);
            }
            depth++;
        }
        return depth;
    }
};

六.题目总结

用单栈可否实现后序遍历求深度

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

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

相关文章

敏感信息泄露到接管云服务器

通过信息收集发现子域为xx.xx.com网站&#xff0c;打开先找功能点&#xff0c;测试登录&#xff0c;是微信扫描登录&#xff0c;自己太菜&#xff0c;测试一圈没测出来什么 指纹识别发现是js开发&#xff0c;如果登录或者找回密码不是扫码登录的话&#xff0c;八成是前端验证&a…

由浅到深认识C语言(9):动态内存分配

该文章Github地址&#xff1a;https://github.com/AntonyCheng/c-notes 在此介绍一下作者开源的SpringBoot项目初始化模板&#xff08;Github仓库地址&#xff1a;https://github.com/AntonyCheng/spring-boot-init-template & CSDN文章地址&#xff1a;https://blog.csdn…

深度解读:如何解决Image-to-Video模型视频生成模糊的问题?

Diffusion Models视频生成-博客汇总 前言&#xff1a;目前Image-to-Video的视频生成模型&#xff0c;图片一般会经过VAE Encoder和Image precessor&#xff0c;导致图片中的信息会受到较大损失&#xff0c;生成的视频在细节信息上与输入的图片有较大的出入。这篇博客结合最新的…

Docker 哲学 - docker-compose.yml 管理多个容器

compose 启动容器的 volume 和 network名字的生成规则 如果在 docker-compose.yml 文件中没有明确定义 networks&#xff0c;Docker Compose 会默认为所有服务创建一个默认的网络。 如果你想自定义网络&#xff0c;你可以在 docker-compose.yml 文件的顶级定义 networks 2、com…

【Spring Cloud】Sentinel限流

控制台下载https://github.com/alibaba/Sentinel/releases # 控制台启动 java -Dserver.port10888 -Dcsp.sentinel.dashboard.serverlocalhost:10888 -Dproject.namesentinel-dashboard -jar sentinel-dashboard.jar引入依赖 <dependency><groupId>com.alibaba.c…

RedisCluster集群中的插槽为什么是16384个?

RedisCluster集群中的插槽为什么是16384个&#xff1f; CRC16的算法原理。 1.根据CRC16的标准选择初值CRCIn的值2.将数据的第一个字节与CRCIn高8位异或3.判断最高位&#xff0c;若该位为0左移一位&#xff0c;若为1左移一位再与多项式Hex码异或4.重复3至9位全部移位计算结束5…

【ArcGIS 脚本工具】强制移动要素类,绕过空间参考不一致

作为一个合格的数据管家&#xff0c;自然要让自己的数据库井井有条。 于是想着整理一下数据库里面的七零八落的要素类&#xff0c;按 数据库-要素数据集-要素类 的方式整理。 但是将要素类移动到要素数据集内的时候经常会出现下面的报错。 这大概率是因为要素类的坐标系与目标…

【数据库】基础操作

系列文章目录 &#x1f308;座右铭&#x1f308;&#xff1a;人的一生这么长、你凭什么用短短的几年去衡量自己的一生&#xff01; &#x1f495;个人主页:清灵白羽 漾情天殇_计算机底层原理,深度解析C,自顶向下看Java-CSDN博客 ❤️相关文章❤️&#xff1a;清灵白羽 漾情天…

一、yocto 编译raspberrypi 4B并启动

yocto 编译raspberrypi 4B并启动 yocto 编译raspberrypi 4B并启动环境准备代码下载编译及配置烧录 yocto 编译raspberrypi 4B并启动 本篇文章为基于raspberrypi 4B单板的yocto实战系列的开篇之作。 环境准备 最近到手一个树莓派4B&#xff0c;准备拿来玩一玩&#xff0c;下面…

电动工具直流调速专用集成电路芯片S069——具有电源电压范围宽、功耗小、抗干扰能力强等特点

GS069是CMOS工艺、电动工具直流调速专用集成电路。具有电源电压范围宽、功耗小、抗干扰能力强等特点。 应用范围&#xff1a;广泛应用于各种电动工具。 02 产品基本参数 03 产品应用 1、应用图&#xff1a; 2、测试参数&#xff1a;&#xff08;VCC9V&#xff0c;RL2K&#x…

osgEarth学习笔记1-安装osgEarth开发环境

原文链接 本文主要是为了防止丢失&#xff0c;做一些记录&#xff0c;仅供个人学习使用。 QGis的学习和使用基本告一段落了。日常的应用已经离不开QGis了&#xff0c;常用的QGis-API和跨平台的QTQGis开发已经十分熟练了。涉及遥感和GIS领域的二维可视化、数据处理使用QT搭配Q…

C语言例3-18:使用关系表达式的例子

关系表达式的一般形式&#xff1a; 表达式 关系运算符 表达式 最初代码如下&#xff1a; #include<stdio.h> int main(void) {int i3,j4,k5;float f11.0, f22.1;char c1a, c2d; //a(97) d(100)printf("i>j 的结果为&#xff1a…

深度学习——微积分基础

目录 1、导数和微分 1.1 定义函数&#xff1a; 1.2 趋近过程&#xff1a; 1.3 绘图表示&#xff1a; 2、偏导数 3、梯度 4、链式法则 5、学习心得 在2500年前&#xff0c;古希腊人把一个多边形分成三角形&#xff0c;并把它们的面积相加&#xff0c;才找到计算多边形面积…

Vue3:标签的ref属性用法

一、情景说明 我们在写前端页面的时候&#xff0c;肯定会遇到获取DOM内容的情况。 以往&#xff0c;我们是用原生的js方法去获取&#xff0c;如document.getXxxx 但是&#xff0c;这中方法会有个问题&#xff0c;如果父组件和子组件的id相同&#xff0c;则会出错。 在Vue3中&…

Unity游戏项目接广告

Unity游戏项目中接入GoogleAdMob 先看效果图 接入测试横幅广告&#xff0c;代码如下&#xff1a; using System.Collections; using System.Collections.Generic; using UnityEngine; using GoogleMobileAds.Api; using System;public class GoogleAdMobManager : MonoBehavi…

观察者模式的理解和引用

1.前言 在之前的H5小游戏中&#xff0c;对于长连接发送的不同类型数据包的处理&#xff0c;是通过switch语句进行处理的&#xff0c;于是在自己的代码中出现了大量的case分支&#xff0c;不方便进行维护和后期的版本迭代。于是在老师的指导下&#xff0c;开始寻求使用观察者模…

【深度学习】滴滴出行-交通场景目标检测

案例5&#xff1a;滴滴出行-交通场景目标检测 相关知识点&#xff1a;目标检测、开源框架的配置和使用&#xff08;mmdetection, mmcv&#xff09; 1 任务目标 1.1 任务和数据简介 本次案例将使用深度学习技术来完成城市交通场景下的目标检测任务&#xff0c;案例所使用的数…

CentOS7 安装ErLang语言环境

在线搜索适合当前linux系统的epel在线安装。 yum -y install epel-release下载erlang-solutions安装包。 wget https://packages.erlang-solutions.com/erlang-solutions-1.0-1.noarch.rpm离线安装erlang-solutions安装包。 rpm -Uvh erlang-solutions-1.0-1.noarch.rpm在线…

项目性能优化—使用JMeter压测SpringBoot项目

项目性能优化—使用JMeter压测SpringBoot项目 我们的压力测试架构图如下&#xff1a; 配置JMeter 在JMeter的bin目录&#xff0c;双击jmeter.bat 新建一个测试计划&#xff0c;并右键添加线程组&#xff1a; 进行配置 一共会发生4万次请求。 ctrl s保存&#xff1b; 添加h…

Aigtek电压放大器的作用及优点是什么

电压放大器是电子技术领域中重要的设备&#xff0c;其作用是将输入信号的电压放大到所需的输出电压水平。电压放大器具有多种优点&#xff0c;下面安泰电子将详细介绍其作用及主要优点。 电压放大器的主要作用是增加信号的电压幅值。通过放大信号的电压&#xff0c;可以增强信号…