《剑指offer》面试题55 - I. 二叉树的深度
2024-10-16 05:15:45
问题描述
输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。
例如:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
提示:
节点总数 <= 10000
代码
/**
* 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:
int maxDepth(TreeNode* root) {
if(!root)return 0;
int ans = 0,size;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
size = q.size();
for(int i = 0; i < size; ++i)
{
TreeNode* node = q.front();
q.pop();
if(node->left)q.push(node->left);
if(node->right)q.push(node->right);
}
++ans;
}
return ans;
}
};
结果
执行用时 :12 ms, 在所有 C++ 提交中击败了75.81%的用户
内存消耗 :19 MB, 在所有 C++ 提交中击败了100.00%的用户
代码
/**
* 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:
int maxnum = 0;
int maxDepth(TreeNode* root) {
if(!root)return 0;
fun(root,1);
return maxnum;
}
void fun(TreeNode* root,int level)
{
if(!root->left && !root->right)maxnum = max(maxnum,level);
if(root->left)fun(root->left,level+1);
if(root->right)fun(root->right,level+1);
}
};
结果
执行用时 :20 ms, 在所有 C++ 提交中击败了25.33%的用户
内存消耗 :19.2 MB, 在所有 C++ 提交中击败了100.00%的用户
最新文章
- 关于 Xcode8打印JSON的时候,NSLog控制台显示不完整
- Activity详解三 启动activity并返回结果
- asp.net中打印指定控件内容
- tomcat证书配置(来源于http://my.oschina.net/zhxm/blog/161159)
- 文件上传ajaxfileupload.js插件
- Apache 日志分析(一)
- cf475A Bayan Bus
- POJ 3667 splay区间盘整运动
- JS学习一
- 将String转换为其表示的路径画到屏幕上
- spring与mybatis(oracle)整合
- 执行大SQL脚本方法
- Git学习(二)Git命令
- 百度编辑器UEditor使用方法
- Solr和Lucene的区别?
- Cannot attach the file as database
- PAT 乙级 1070 结绳(25) C++版
- Windows 7/Vista下安装Oracle Developer Suit遇到的几个问题
- PyCharm+Eclipse共用Anaconda的数据科学环境
- 关于IBatisNet的配置文件中数据库连接字符串加密处理
热门文章
- ☕【Java深层系列】「技术盲区」让我们一起去挑战一下如何读取一个较大或者超大的文件数据!
- 数据库函数(Excel函数集团)
- 第四届“传智杯”全国大学生IT技能大赛题解
- BUGKU web刷题记录
- java 编程基础 反射方式获取泛型的类型Fileld.getGenericType() 或Method.getGenericParameterTypes(); (ParameterizedType) ;getActualTypeArguments()
- java 常用类库:BigInteger大整数;BigDecimal大小数(解决double精度损失);
- java web 404错误页面配置
- 十行代码搭建基于.NET6三维应用程序
- UDP&;串口调试助手用法(4)
- 【LeetCode】 202. Happy Number 解题报告(Java & Python & C++)