111. 二叉树的最小深度
难度简单689
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
图一
第一次错误解法：
这种解法无法解决如下图中的情况
image.png
这种情况下，返回的答案是1
# 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
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
else:
return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
第二次错误
修改以上错误，把节点为空时的返回值变大（私以为比1大即可，但是后续发现是错误的），
# 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
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 100
if not root.left and not root.right:
return 1
else:
return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
我的最终解法：
提交之后，发现有个结构如图一，但是有1800多个节点的用例，没有通过，返回值是101，这时候我才意识到，节点空时的返回值不是比1大即可，随着递归的进行，必须要比最深层那个空节点返回值大才行，那么就无穷大啦！
另外，第一次根节点为空的情况没法判断了，改成子函数形式。
# 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
class Solution:
def minDepth(self, root: TreeNode) -> int:
def minDepthFun(root):
if not root:
return float('inf') # 设置为无穷大
if not root.left and not root.right:
return 1
else:
return 1 + min(minDepthFun(root.left), minDepthFun(root.right))
if not root:
return 0
else:
return minDepthFun(root)
官方解法
官方解法的关键在于，将左右节点为空的情况分别讨论，分别递归
深度优先遍历
对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。
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
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
广度优先遍历
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
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
