104 二叉树的最大深度_王培琳的博客-程序员宅基地

技术标签: LeetCode  

题目描述:
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],
在这里插入图片描述
返回它的最大深度 3 。

方法1:递归
主要思路:
(1)正常的先序遍历递归处理;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    
public:

    void helper(TreeNode* root,int& cur_depth,int& max_depth){
    
    	//终止条件
        if(root==NULL)
            return ;
        ++cur_depth;//深度增加
        //若是叶子结点,则更新可能的最大值
        if(root->left==NULL&&root->right==NULL){
    
            max_depth=max(max_depth,cur_depth);
        }
        //左右子树遍历
        helper(root->left,cur_depth,max_depth);
        helper(root->right,cur_depth,max_depth);
        --cur_depth;//因为是引用,使用类似回溯,复原数值
    }

    int maxDepth(TreeNode* root) {
    
    	//处理特殊的情形
        if(root==NULL)
            return 0;
        if(root->left==NULL&&root->right==NULL)
            return 1;
        //两个辅助变量,因为使用的是引用处理的
        int max_depth=0;
        int cur_depth=0;
        //调用递归函数
        helper(root,cur_depth,max_depth);
        return max_depth;
    }
};
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44171872/article/details/107464063

智能推荐

服务框架HSF分析之三Consumer启动和处理_iteye_14085的博客-程序员宅基地

 前两篇文章为大家带来了HSF容器启动和Porvider的分享。这篇来分析下consumer端的运行机制。一. Consumer的启动1.     服务代理在HSFSpringConsumer的启动中会返回一个HSFServiceProxy的jdk动态代理,后续调用其实都是通过这个代理类来实现的。InvocationHandler handler = newHSFServ...

关于spring、hibernate 整合错误,请大神们帮忙看看哪里出错了_sinat_34810781的博客-程序员宅基地

在网上找了个项目,准备做 spring + hibernate 整合测试的时候,update()方法出现问题了。update()是用Spring+Hibernate,程序不报错,但是数据库里面的数据没有任何变化。save()是没有任何问题的,save()是 hibernate写的。@RunWith(SpringJUnit4ClassRunner.class) @ContextConfigur

Spring MVC如何访问到静态的文件,如jpg,js,css,png,gif? _iteye_19209的博客-程序员宅基地

如果你的DispatcherServlet拦截 *.do这样的URL,就不存在访问不到静态资源的问题。如果你的DispatcherServlet拦截“/”,拦截了所有的请求,同时对*.js,*.jpg的访问也就被拦截了。目的:可以正常访问静态文件,不要找不到静态文件报404。  方案一:激活Tomcat的defaultServlet来处理静态文件 Xml代码<...

前端与后台交互的数据格式有哪些?_say个嗨呀的博客-程序员宅基地_常用前后端数据交互格式

前后端的交互数据格式有:json、xml及from表格;现在主流的数据格式是json;xml基本不怎么用了;from不常用但是要知道

4万程序员学了10万次的课程,今天,曝光背后的讲师!_csdn业界要闻的博客-程序员宅基地

戳蓝字“CSDN云计算”关注我们哦!进入付费时代,如今我们看似只要招招手,一切知识随手可得:管理艺术、人际关系、婚姻恋爱,拆解名著……可程序员依旧苦恼。由于开发技术迭代过快,各大厂自研...

[转载]Codeblocks+MinGW+wxWidgets搭建方法_weixin_30485291的博客-程序员宅基地

Code::Block、MinGW 和 wxWidgets 分别是三个著名的开源项目,分别是 IDE、编译器和界面库。由这三样搭建起来的全开源纯c++开发环境,功能不逊色于Visual C++,由于是开源的,这样的环境还是免费的,并且是跨平台的。^-^下面说一下在 Windows 下的搭建过程:一、编译器MinGW是指只用自由软件来生成纯粹的Win32可执行文件的编译环境,它是Minimalis...

随便推点

二叉搜索树(二叉排序树)_爱敲代码的三毛的博客-程序员宅基地_二叉搜索树

一.概念二叉搜索树又称二叉排序树,具有以下性质:若它的左子树不为空,则左子树上所有节点的值都小于根节点的值若它的右子树不为空,则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树注意:二叉搜索树中序遍历的结果是有序的二、基本操作1.查找元素思路:二叉搜索树的左子树永远是比根节点小的,而它的右子树则都是比根节点大的值。当前节点比要找的大就往左走,当前元素比要找的小就往右走 public Node search(int key) { if(root ==

动手学深度学习之文本预处理_哈哈哈捧场王的博客-程序员宅基地_文本预处理 深度学习

文本预处理import collectionsimport refrom d2l import torch as d2l将数据集读取到由文本行组成的列表中d2l.DATA_HUB['time_machine'] = (d2l.DATA_URL + 'timemachine.txt', '090b5e7e70c295757f55df93cb0a180b9691891a') # load一本书def read_time_machi

Python 把多个 MP4 合成一个视频_AI悦创的博客-程序员宅基地_python将多个视频合成一个视频

这两天群里有个小伙伴有一个需求, 就是把很多个视频文件 合并成一个. 期间也找了各种软件, 如格式工厂, 但是只能一次合成50个文件, 小伙伴有几千个文件需要合成, 太繁琐; 又比如会声会影, 这个剪辑是很强大, 但是软件也很大, 对电脑配置要求也高. 我只需要拼接功能, 割鸡焉用牛刀?人生苦短 我用 Python????转念一想, Python 也很擅长图形处理, 那处理视频也不在话下吧, 于是就上网搜了搜, 果然找到了简单的办法~开始安装使用主要是利用 moviepy 这个库, 里面提供了丰富的

设计模式——原型模式(Prototype)(浅克隆、深克隆)_蒋含竹的博客-程序员宅基地

文章目录原型设计模式,克隆一个苹果Code 克隆用的Apple类苹果基类可克隆的苹果(用于浅克隆)可克隆的苹果(用于深克隆)可序列化的苹果(用于深克隆)家庭作业类(用于测试原型模式性能)克隆Test浅克隆测试深克隆测试序列化、反序列化的方式实现深克隆 测试原型模式的性能测试代码:GitHub原型设计模式,克隆一个苹果Code 克隆用的Apple类苹果基类import jav...

Vue组件(一) - 二次封装ElementUI实现tree树形组件_劰的劰的博客-程序员宅基地

文章目录功能描述代码base-tree.vue:treeDemo.vue:功能描述基础功能同el-tree代码base-tree.vue:<!-- * @Description: 公共树组件 * @Author: HMM * @Date: 2021-01-11 16:23:23 * @FilePath: base-tree.vue变量: expandNode:是否展开所有节点 isShowFilter: 是否需要节点过滤 treeProps: 树形结构配置项事件: @h

Python - 常用的PyCharm的快捷键和使用场景介绍_weixin_46728614的博客-程序员宅基地

关于PyCharm的快捷键,由于数量众多,差不多有100个,相信几乎没有人会记住所有,每个人都会有自己顺手的几个,这里我将自己用着顺手,不别扭的快捷键分享出来,同时分享在哪里可以找到所有的快捷键。一、创建和编辑的需要智能跳转到下一步:Ctrl + Shift + Enter使用场景:1)当你写函数时,写完def,按下以上快捷键,括号,冒号都自动加上,并且光标自动回到函数名字填写处;2)当你代码写到最后一行,且在字符串里面写完,这个时候按下以上快捷键,光标智能换行,不影响目前的字符串等信息,需要

推荐文章

热门文章

相关标签