LeetCode 111. 二叉树的最小深度

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 111. 二叉树的最小深度

思路分析

我们可以使用广度优先搜索来找到二叉树的最小深度。广度优先搜索的特点是逐层遍历树，因此当我们找到第一个叶子节点时，当前的深度就是最小深度。具体步骤如下：

初始化一个队列，将根节点入队。

进行循环，直到队列为空：

取出队列的第一个节点。

检查当前节点是否是叶子节点：

如果是叶子节点，返回当前深度。

将当前节点的左右子节点（如果存在）入队，并增加深度。

如果队列为空，返回 0（表示树为空）。

参考代码

func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	queue := []*TreeNode{root}
	depth := 0

	for len(queue) > 0 {
		size := len(queue)
		depth++ // 深度加一
		
		for i := 0; i < size; i++ {
			node := queue[0]  // 取出队列的第一个节点
			queue = queue[1:] // 更新队列

			// 检查是否是叶子节点
			if node.Left == nil && node.Right == nil {
				return depth // 返回当前深度
			}

			// 将左右子节点入队
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
	}

	return depth
}

时间复杂度：O (n)，其中 n 是树中节点的数量。我们需要遍历每个节点一次。

空间复杂度：O (w)，其中 w 是树的最大宽度。在最坏情况下，队列可能会存储树的所有节点。

func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	// 如果左子树为空，递归右子树
	if root.Left == nil {
		return minDepth(root.Right) + 1
	}
	// 如果右子树为空，递归左子树
	if root.Right == nil {
		return minDepth(root.Left) + 1
	}

	// 递归计算左右子树的最小深度
	leftDepth := minDepth(root.Left)
	rightDepth := minDepth(root.Right)

	// 返回较小的深度加一
	return min(leftDepth, rightDepth) + 1
}

时间复杂度：O(N)，其中 N 是二叉树的节点数。每个节点遍历一次。

空间复杂度：O(H)，其中 H 是二叉树的高度，递归调用栈的深度。

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/76438130