(剑指Offer)面试题39:二叉树的深度
2024-08-28 22:11:07
题目:
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
结点的定义如下:
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
};
思路:
对于树的问题基本都可以通过递归来解决。
一棵二叉树的深度,等于它的左子树深度和右子树深度的较大者+1;
递归的结束条件就是:该结点为空,深度为0;
代码:
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
}; int TreeDepth(TreeNode* pRoot){
if(pRoot==NULL)
return 0;
int left=TreeDepth(pRoot->left);
int right=TreeDepth(pRoot->right);
return left>right?(left+1):(right+1);
}
在线测试OJ:
http://www.nowcoder.com/books/coding-interviews/435fb86331474282a3499955f0a41e8b?rp=2
AC代码:
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
if(pRoot==NULL)
return 0;
int left=TreeDepth(pRoot->left);
int right=TreeDepth(pRoot->right); return left>right?(left+1):(right+1);
}
};
最新文章
- stm32定时器实现60秒定时秒表
- jquery this 和 event.target 区别
- 手机端开发icon的问题
- 朝花夕拾-android 从手机选择图片或拍照设置头像
- final specifier (since C++11)
- Java 线程池学习
- fork();
- CSDN博客排名第一名,何许人也
- /usr 的由来及/usr目录结
- 关于java中的==,equals()
- 在ASP.NET Core Web API中为RESTful服务增加对HAL的支持
- Linux 进程间通信(包含一个经典的生产者消费者实例代码)
- 慢慢来写SpringMVC基本项目
- 201621123040《Java程序设计》第4周学习总结
- 6. VIM 系列 - 全局搜索(ctrlsf.vim)
- 1.8分布式集群模式基础(VM安装多台服务器)
- 2019.03.25 bzoj4572: [Scoi2016]围棋(轮廓线dp)
- Microsoft Azure Machine Learning Studio
- table 如何不越过父级div
- Python 函数的作用域