个人主页：清风莫追
系列专栏：牛客刷题——数据结构与算法
推荐一款面试、刷题神器牛客网：👉点击加入刷题大军👈
1.题目描述
描述
求给定二叉树的最大深度，
深度是指树的根节点到任一叶子节点路径上节点的数量。
最大深度是所有叶子节点的深度的最大值。
（注：叶子节点是指没有子节点的节点。）
数据范围：
0
≤
n
≤
100000
0≤n≤100000
0≤n≤100000，树上每个节点的val满足
∣
v
a
l
∣
≤
100
∣val∣≤100
∣val∣≤100
要求： 空间复杂度
O
(
1
)
O
(
1
)
O(1)O(1)
O(1)O(1),时间复杂度
O
(
n
)
O
(
n
)
O(n)O(n)
O(n)O(n)
注：示例中的输入是按照二叉树的层序遍历顺序，# 表示空。
2.算法设计思路
可以用递归的思路来解这个问题：
-
二叉树的最大深度
=
m
a
x
{
左子树最大深度，右子树最大深度
}
+
1
二叉树的最大深度 = max\{左子树最大深度，右子树最大深度\}+1
二叉树的最大深度=max{左子树最大深度，右子树最大深度}+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.运行结果
成功通过！
结束语：
今天的分享就到这里啦，快来加入刷题大军叭！
👉点击开始刷题学习👈
感谢阅读
个人主页：清风莫追
CSDN话题挑战赛第2期
参赛话题：学习笔记
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/114808.html
