【Leetcode】二叉树的最小深度
2024-09-05 17:57:21
题目：
给定一个二叉树，找出其最小深度。
注意最小深度的定义！
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
一、递归法
时间复杂度：O(n)。需要遍历每一个节点。
空间复杂度：最差情况下，当一棵树是非平衡树的时候，例如每个节点都只有一个孩子，树的高度为n，会产生n次递归调用，因此栈的空间开销是O(N)。但在最好情况下，树的高度只有log(n)，栈的空间开销是O(log(N))。
/**
* 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 minDepth(TreeNode* root) {
if (root == NULL)
return ; if( (root->left == NULL) && (root->right == NULL) )
return ; int depthL = INT_MAX;
int depthR = INT_MAX; if(root->left != NULL)
depthL = minDepth(root->left);
if(root->right != NULL)
depthR = minDepth(root->right); int depth = min( depthL, depthR ) + ;
return depth;
}
};
二、宽度优先搜索
使用FIFO的数据结构queue存储树节点，从而实现对树节点自上而下的遍历。
时间复杂度：O(N)。完全二叉树的情况下，需要对 n/2 个节点进行遍历。非平衡树的情况下，例如每个节点只有1个孩子节点，则需要遍历所有节点。
空间复杂度：O(N)。完全二叉树的情况下，queue容器中最多需要存储 n/2 个节点。非平衡树的情况下，例如每个节点只有1个孩子节点，则queue容器中最多只存储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:
int minDepth(TreeNode* root) {
if(root == NULL)
return ; queue<TreeNode*> q;
q.push(root);
int depth = ; while(!q.empty()) {
int len = q.size(); for(int i = ; i < len; ++i) {
TreeNode* node = q.front();
q.pop(); int num = ; if(node->left != NULL) {
q.push(node->left);
num += ;
}
if(node->right != NULL) {
q.push(node->right);
num += ;
} if(num == )
return depth + ;
}
depth++;
}
return depth;
}
};
最新文章
- Error invoking SqlProvider method (com.github.abel533.mapper.MapperProvider.dynamicSQL). Cause: java.lang.InstantiationException: com.github.abel533.mapper.MapperProvider
- RStudio技巧01_美化RStudio的帮助页面
- Guava学习笔记：Guava新增集合类型-Bimap
- lintcode：移动零
- （转载）javascript转自世纪流年blog
- 文字排版--下划线(text-decoration:underline)
- C# 操作NPOI导入导出
- sql事务，在sql2000里判断执行是否成功用@@ERROR 判断
- 数据持久层框架iBatis, Hibernate 与 JPA 比较
- sync命令
- 极光推送,极光IM使用指南（AndroidStudio）
- bootstrap使用模板
- ubuntu下安装PyCharm的两种方式
- js 格式化带时区的日期
- JS中=>，>>>是什么意思
- ArrayList集合、String[]数组、String字符串
- Spring Boot 历史
- CSS样式----CSS样式表的继承性和层叠性（图文详解）
- 线段树+单调栈+前缀和--2019icpc南昌网络赛I
- jquery操作select(选中，取值)