大家好我是你们的好朋友，大数据老虾。相遇是缘，既然来了就拎着小板凳坐下来一起唠会儿，如果在文中有所收获，请别忘了一键三连，动动你发财的小手，你的鼓励，是我创作的动力！废话不多说，直接 开干吧！
树-二叉树的最小深度PS：文末干货，记得拎着小板凳离开的时候也给它顺走 藍
座右铭：“懒”对一个人的毁灭性有多大，早起的重要性就多大。
二叉树的最小深度
题目方法1：深度优先搜索Java实现代码
复杂度分析 Python实现代码方法2：广度优先搜索Java实现代码
复杂度分析 Python实现代码文末彩蛋朗
二叉树的最小深度 题目给出一个二叉树，找出最小深度。
PS：最小深度是指从根节点到最近叶子节点的最短路径上的节点数量，叶子节点是指没有子节点的节点
示例1：
input：root = [3, 9, 20, null, null, 15, 7] output：2
示例2：
input：root = [2, null, 3, null, 4, null, 5, null, 6] output：5方法1：深度优先搜索
解析：
使用深度优先搜索的方法，遍历整棵树，记录最小深度
对于每一个非叶子节点，只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题
Java实现代码class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int min_depth = Integer.MAX_VALUE;
if (root.left != null) {
min_depth = Math.min(minDepth(root.left), min_depth);
}
if (root.right != null) {
min_depth = Math.min(minDepth(root.right), min_depth);
}
return min_depth + 1;
}
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
复杂度分析
时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。
空间复杂度：O(H)，其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(logN)。
Python实现代码class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
min_depth = 10**9
if root.left:
min_depth = min(self.minDepth(root.left), min_depth)
if root.right:
min_depth = min(self.minDepth(root.right), min_depth)
return min_depth + 1
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
方法2：广度优先搜索
使用广度优先搜索的方法，遍历整棵树
当找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。
Java实现代码class Solution {
class QueueNode {
TreeNode node;
int depth;
public QueueNode(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue queue = new linkedList();
queue.offer(new QueueNode(root, 1));
while (!queue.isEmpty()) {
QueueNode nodeDepth = queue.poll();
TreeNode node = nodeDepth.node;
int depth = nodeDepth.depth;
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) {
queue.offer(new QueueNode(node.left, depth + 1));
}
if (node.right != null) {
queue.offer(new QueueNode(node.right, depth + 1));
}
}
return 0;
}
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
复杂度分析
时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。
空间复杂度：O(N)，其中 N 是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。
Python实现代码class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
que = collections.deque([(root, 1)])
while que:
node, depth = que.popleft()
if not node.left and not node.right:
return depth
if node.left:
que.append((node.left, depth + 1))
if node.right:
que.append((node.right, depth + 1))
return 0
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
朗✨给各位朋友安利一下平时收集的各种学习资料！！！有需要的朋友点击一下⏩传送门，自行领取。程序员经典名言：“收藏了就等于学会啦”。 做人也要像蜡烛一样，在有限的一生中有一分热发一份光，给人以光明，给人以温暖！
图灵程序丛书300+
Linux实战100讲
Linux书籍
计算机基础硬核总结
计算机基础相关书籍
操作系统硬核总结
Java自学宝典
Java学习资料
Java硬核资料
Java面试必备
Java面试深度剖析
阿里巴巴Java开发手册
MySQL入门资料
MySQL进阶资料
深入浅出的SQL
Go语言书籍
我的个人仓库：私人仓库
