难度: Easy
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6] 输出:5
提示:
- 树中节点数的范围在
[0, 105]
内 -1000 <= Node.val <= 1000
难度: Easy
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6] 输出:5
提示:
[0, 105]
内-1000 <= Node.val <= 1000
运行时间: 480 ms
内存: 51.7 MB
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right from collections import deque class Solution: def minDepth(self, root: TreeNode) -> int: if root is None: return 0 q = deque() q.append(root) floor = 1 while q: size = len(q) for _ in range(size): node = q.popleft() if node.left is None and node.right is None: return floor if node.left: q.append(node.left) if node.right: q.append(node.right) floor += 1
该题解使用广度优先搜索(BFS)的方法来解决二叉树的最小深度问题。具体思路如下: 1. 如果根节点为空,直接返回深度0。 2. 创建一个队列,并将根节点加入队列。 3. 初始化深度为1。 4. 当队列不为空时,进行以下操作: a. 获取当前队列的大小,表示当前层的节点数。 b. 遍历当前层的所有节点: - 从队列中取出节点。 - 如果该节点是叶子节点(左右子节点都为空),则返回当前深度。 - 如果该节点有左子节点,将左子节点加入队列。 - 如果该节点有右子节点,将右子节点加入队列。 c. 深度加1,继续下一层的遍历。
时间复杂度: O(n)
空间复杂度: O(w)
from collections import deque class Solution: def minDepth(self, root: TreeNode) -> int: # 如果根节点为空,直接返回深度0 if root is None: return 0 # 创建一个队列,并将根节点加入队列 q = deque() q.append(root) # 初始化深度为1 floor = 1 # 当队列不为空时,进行遍历 while q: # 获取当前队列的大小,表示当前层的节点数 size = len(q) # 遍历当前层的所有节点 for _ in range(size): # 从队列中取出节点 node = q.popleft() # 如果该节点是叶子节点,则返回当前深度 if node.left is None and node.right is None: return floor # 如果该节点有左子节点,将左子节点加入队列 if node.left: q.append(node.left) # 如果该节点有右子节点,将右子节点加入队列 if node.right: q.append(node.right) # 深度加1,继续下一层的遍历 floor += 1
在BFS中,我通过层序遍历来确保总是首先到达最近的叶子节点。因为BFS是按层(从根节点到叶子节点)进行的,所以确保了一旦遇到任何叶子节点,它必定是最近的叶子节点,因此可以立即返回其深度。
选择BFS的原因是它更适合于寻找最小深度。在使用DFS时,我们可能会首先深入到树的一个深层分支,而这个分支可能不包含最近的叶子节点。而BFS从根节点开始逐层向下搜索,一旦找到叶子节点,就可以确保这是到达叶子节点的最短路径。
在最坏情况下,队列中可能会包含与二叉树的最宽层一样多的节点。这种情况通常发生在每个节点都有两个子节点的完全二叉树中。例如,在完全二叉树的最后一层,如果树高为h,最后一层可能包含2^(h-1)个节点。
在节点出队后立即检查它是否是叶子节点可以避免不必要的操作,因为一旦确定一个节点是叶子节点,我们就可以返回其深度,不需要进一步探索其子节点。在将子节点加入队列前进行检查是不合适的,因为我们需要首先确认当前节点是否为叶子节点;如果不是,我们才需要考虑其子节点。