[LeetCode] 111. Minimum Depth of Binary Tree 二叉树的最小深度
2024-10-21 15:53:05
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
给一个二叉树,找出它的最小深度。最小深度是从根节点向下到最近的叶节点的最短路径,就是最短路径的节点个数。
解法1:DFS
解法2: BFS
Java: DFS, Time Complexity: O(n), Space Complexity: O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null) {
return 1 + minDepth(root.right);
} else if (root.right == null) {
return 1 + minDepth(root.left);
} else {
return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}
}
}
Java: BFS
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int curLevel = 1, nextLevel = 0;
int depth = 1; while (!q.isEmpty()) {
TreeNode node = q.poll();
curLevel--;
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) {
q.offer(node.left);
nextLevel++;
}
if (node.right != null) {
q.offer(node.right);
nextLevel++;
}
if (curLevel == 0) {
curLevel = nextLevel;
nextLevel = 0;
depth++;
}
}
return depth;
}
}
Python:
class Solution(object):
def minDepth(root):
if root is None:
return 0 # Base Case : Leaf node.This acoounts for height = 1
if root.left is None and root.right is None:
return 1 if root.left is None:
return minDepth(root.right) + 1 if root.right is None:
return minDepth(root.left) + 1 return min(minDepth(root.left), minDepth(root.right)) + 1
Python:
class Solution:
# @param root, a tree node
# @return an integer
def minDepth(self, root):
if root is None:
return 0 if root.left and root.right:
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
else:
return max(self.minDepth(root.left), self.minDepth(root.right)) + 1
C++:
/**
* Definition for binary tree
* 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 0;
if (root->left == NULL && root->right == NULL) return 1; if (root->left == NULL) return minDepth(root->right) + 1;
else if (root->right == NULL) return minDepth(root->left) + 1;
else return 1 + min(minDepth(root->left), minDepth(root->right));
} };
类似题目:
[LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度
All LeetCode Questions List 题目汇总
最新文章
- spring aop对service层日志和异常的处理
- jQuery中json对象与json字符串互换
- Windows请求连接 Vmware+Ubuntu14被拒绝 的幽怨诉说
- NavigationController
- android studio 使用SVN 锁定文件,防止别人修改(基于Android studio 1.4 )
- Spring MVC学习笔记——JSR303介绍及最佳实践
- jQuery取复选框值、下拉列表里面的属性值、取单选按钮的属性值、全选按钮、JSON存储、*去空格
- iOS开发网络篇—发送json数据给服务器以及多值参数
- C# login with cookie and fiddler2
- js类的几种写法
- #include <;locale.h>; #include <;locale>;
- Java面试题收集学习整理1
- 设计模式 - 装饰者模式(Decorator Pattern) Java的IO类 用法
- 2017-2-17,c#基础,输入输出,定义变量,变量赋值,int.Parse的基础理解,在本的初学者也能看懂(未完待续)
- python +Django 搭建web开发环境初步,显示当前时间
- 写在19年初的后端社招面试经历(两年经验): 蚂蚁 头条 PingCAP
- 构建之法-软件测试+质量保障+稳定和发布阶段+IT行业的创新+人、绩效和职业道德
- DOS批处理中%cd%和%~dp0的异同分析
- Tomcat多站点部署方式
- Win10 Ubuntu 双系统 卸载 Ubuntu