leet code. 104(二叉树的最大深度)-程序员宅基地

Q：给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。

因为没有做过关于树方面的算法题，所以我先随便找了一篇树的遍历看了看，主要是讲了三种遍历方法的非递归方法。应该跟这道题没有啥关系，先放在这做个记录。

【图解数据结构】二叉树遍历
方法一： 递归
应该是用 深度优先搜索 （DFS）和 递归 算法来解这道题。
深度优先算法，我觉得简单来说就是，当有很多条链的时候，先完整的搜索完一条链，再搜索下一条。每个结点只能访问一次。

先从最开始访问，然后回溯到起点，然后看看起点有没有相邻的结点还没被访问，如果有，就访问另一条路，没有就结束。

【DFS】深度优先搜索递归方式讲解

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        int count,lefttree,righttree;
        lefttree=maxDepth(root->left);
        righttree=maxDepth(root->right);
        return max(lefttree,righttree)+1;
    }
};

运行的比较慢，看了一下官网的复杂度分析，粘了过来。这里函数调用自己就是递归。递归我的理解就是，先逐个从外往里调用直到不满足条件为止，然后再从里往外挨个计算。if()就是让它停止递归的条件。可以看一下这篇文章。
简单谈谈 C/C++ 递归的思想，实现，以及和循环的关系
在这里插入图片描述方法二 ：迭代
看了官方题解，迭代大概就是用一个队列来存储每一层结点及它的左右孩子。比如，二叉树 [3,9,20,null,null,15,7] 。先把3,9,20,15,7放到队列里，此时队列大小为5，然后挨个看有没有左右孩子，有的话就push进队尾，然后把队头这个pop掉。这个小循环之后。队列变成9.20.15.7.就只包括了第二层和第三层的数。这样不停大循环，直到队列为空停止。每一次小循环都往下走了一层，用一个计数器计数即可。
代码如下：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        queue<TreeNode*> q{
   {root}};
        while (!q.empty()) {
            ++res;
            for (int i = q.size(); i > 0; --i) {
                TreeNode *t = q.front(); q.pop();
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return res;
    }
};

在这里插入图片描述
不知道为啥。最近跑代码都很慢，用了别人的代码，相差也很大。
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/m0_37564139/article/details/87860733

智能推荐

Keras实现层的分离_keras输入图像通道分离-程序员宅基地

文章浏览阅读522次。前言笔者最近在复现Shufflenet Mobilenet 和谷歌最新推出的EfficientNet结构发现各大网络都在往轻巧化方向发展其中一个很关键的，就是Depthwise卷积结构的提出，可以参考我上篇博客而其中Depthwise卷积需要对单独的通道在做一次卷积，而不是多通道上进行累加因此这就涉及到了通道的分离下面我们直接来看代码代码实现import kerasfrom ke..._keras输入图像通道分离

SpringBoot 整合Swagger2 启动异常documentationPluginsBootstrapper NullPointerException_org/springframework/boot/bootstrapper-程序员宅基地

文章浏览阅读815次。SpringBoot 整合Swagger2 启动异常org.springframework.context.ApplicationContextException: Failed to start bean 'documentationPluginsBootstrapper'; nested exception is java.lang.NullPointerException_org/springframework/boot/bootstrapper

IntelliJ IDEA 下载安装配置教程（完整版）_idea安装教程-程序员宅基地

文章浏览阅读10w+次，点赞438次，收藏2.2k次。IntelliJ IDEA 下载安装教程参考:https://blog.csdn.net/HD_hjx/article/details/89931754number_one:官网下载 IntelliJ IDEAnumber_two:开始安装的旅途吧！_idea安装教程

centos7 安装 arl 灯塔_linux 放行5003端口-程序员宅基地

文章浏览阅读4.4k次，点赞4次，收藏20次。灯塔 arl 的安装环境要求：Linux 系统，Ubuntu、Centos等看自己喜欢哪个Python3dockerdocker compose安装安装 Python3yum install -y python3安装 docker参考：https://editor.csdn.net/md/?articleId=115617110安装docker compose参考：https://editor.csdn.net/md/?articleId=115621316安装 arl _linux 放行5003端口

linux共享目录命令 sudo vmhgfs-fuse .host:/ /mnt/hgfs -o nonempty-程序员宅基地

文章浏览阅读7k次。这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入linux共..._sudo vmhgfs-fuse

python操作数据库，fetchone、fetchall_python cursor.fetchall从第一行开始读-程序员宅基地

文章浏览阅读556次。代码如下：fetchonefrom DrugRelationshipData.setting.DBsetting import *# 查找数据库中某个值class SeletMysqlData: def select_data(self,sql): cursor.execute(sql) #需要运行的sql while 1: # 全表循环执行 try: re = cursor.fetcho_python cursor.fetchall从第一行开始读

随便推点

如何批量删除文件的前缀？_rename去除前缀-程序员宅基地

文章浏览阅读1.5k次。工作中如果你获得了很多文件，这些文件都有相同的前缀，有时候我们可能需要将这些相同的前缀删除掉，有没有什么比较好用的方法呢？很多人会回答“很简单啊，只要一个一个文件进行重命名，然后删除这些前缀即可”，确实这个方法很简单，但是也是最耗时的方法，如果有几百个文件需要处理，花费的时间可想而知。其实大可不必这样，我们需要有更简单高效的方法，今天小编就借助一个工具软件，为大家详细介绍如何批量删除文件名中的前缀。跟着我一起学习吧！使用工具软件：优速文件批量重命名软件下载地址：免费下载优速文件批量重命名软件ht_rename去除前缀

【Redis】——引入redis-cluster-proxy使得Redis Cluster对Kubernetes外部可提供服务-程序员宅基地

文章浏览阅读4.9k次，点赞3次，收藏18次。一、前言 这几年云计算发展迅猛，服务容器化在docker和k8s的发展下变成了潮流。无状态服务容器化相对来说较为简单，难得是有状态服务（诸如各数据库）容器化。本文讲讲redis集群容器化后，部署到k8s中怎么暴露服务使得k8s集群外部的服务能够连接redis.本文先说怎么用，再介绍redis-cluster-proxy。二、Redis Cluster容器化需要解决的问题1. Redis Cluster数据持久化 -> 可以通过StatefulSet + PVC来..._redis-cluster-proxy

CNN中卷积层的计算细节_cnn卷积层卷积举例-程序员宅基地

文章浏览阅读727次。原文链接： https://zhuanlan.zhihu.com/p/29119239卷积层尺寸的计算原理输入矩阵格式：四个维度，依次为：样本数、图像高度、图像宽度、图像通道数输出矩阵格式：与..._cnn卷积层卷积举例

关于程序员宅基地文章如何置顶的问题，强烈建议后台新版尽快更新啊~_csdn置顶了几个视频-程序员宅基地

文章浏览阅读547次。事情是这样的相信有很多博主都遇到了博客置顶问题，同样我也遇到了于是就到处找啊找。。。发现找不到！！！询问客服~原来是新版界面还没更新。。。（无语子）直接上教程下面是原话抱歉由于新版主页置顶功能还在优化。您可以点击页面的切换到旧版按钮，在旧版主页中操作。或在文章可在 MP/文章管理（https://mp.csdn.net/console/article） 中设置置顶，在“个人主页-文章”里查看被置顶文章。Salute~【纯·干货】你会用到的论文小助手，不定期持续更新中~..._csdn置顶了几个视频

无法访问微软官方网站的解决方法_ie打不开微软官网-程序员宅基地

文章浏览阅读4w次。------------------------------------无法访问微软官方网站的解决方法--------------------问题症状：⒈无法访问微软相关官方网站 如：（http://update.microsoft.com/）⒉其他网站都能正常访问！--------------------------------------------------------------------------------------------_ie打不开微软官网

Python里用pip install 安装下载的安装包默认缓存位置_pip下载文件存放位置-程序员宅基地

文章浏览阅读9.1k次，点赞6次，收藏25次。Python里用pip install 安装下载的安装包默认缓存位置_pip下载文件存放位置

推荐文章

热门文章

相关标签