【牛客刷题 - 算法】 NC13 二叉树的最大深度

作者：清风莫追

2022 年 10 月 01 日
湖南
本文字数：761 字
阅读完需：约 2 分钟

个人主页：清风莫追系列专栏：牛客刷题——数据结构与算法推荐一款面试、刷题神器牛客网：👉点击加入刷题大军👈

@[toc]

1.题目描述

描述求给定二叉树的最大深度，深度是指树的根节点到任一叶子节点路径上节点的数量。最大深度是所有叶子节点的深度的最大值。（注：叶子节点是指没有子节点的节点。）

数据范围： $0 \leq n \leq 100000$ ，树上每个节点的 val 满足 $∣ v a l ∣ \leq 100$ 要求：空间复杂度 $O (1) O (1)$ ,时间复杂度 $O (n) O (n)$

![在这里插入图片描述](https://img-blog.csdnimg.cn/33a7ffe6db384ef1b77c60685bfa0cb4.png)

注：示例中的输入是按照二叉树的层序遍历顺序，# 表示空。

2.算法设计思路

可以用递归的思路来解这个问题：

$二叉树的最大深度 = m a x 左子树最大深度，右子树最大深度 + 1$

而对于左右子树的最大深度，我们也同样地使用上面的表达式计算。

直到递归到空的树，此时它的深度为 0 ，开始回升。

3.算法实现

注：这里并不是完整代码，而只是核心代码的模式

使用编程语言：C++

/** * struct TreeNode { *  int val; *  struct TreeNode *left; *  struct TreeNode *right; * }; */
class Solution {public:    /**     *      * @param root TreeNode类      * @return int整型     */    int maxDepth(TreeNode* root) {        //到达叶子结点        if(root == nullptr) return 0;
        int max = 0;        int deep1 = maxDepth(root->left) + 1;        int deep2 = maxDepth(root->right) + 1;
        if(deep1 > deep2) max = deep1;        else max = deep2;                return max;    }};

复制代码

4.运行结果

成功通过！

![在这里插入图片描述](https://img-blog.csdnimg.cn/63a8706eb40f41018e1864811b396bcd.png)

结束语：

今天的分享就到这里啦，快来加入刷题大军叭！👉点击开始刷题学习👈

感谢阅读

个人主页：清风莫追

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/c58153d2214c26f382015efb6】。文章转载请联系作者。

清风莫追

关注

还未添加个人签名 2022.08.09 加入

编程一学生

发布

暂无评论

创作场景