## Description

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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
/ \
9  20
/  \
15   7


return its minimum depth = 2.

## Solutions

找到最小的深度，即找到最小的没有左右子结点的那个节点的深度。

### 1. DFS 递归

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
if not root.left and not root.right:
return 1
l = self.minDepth(root.left)
r = self.minDepth(root.right)
if not root.left:
return 1 + r
if not root.right:
return 1 + l
return 1 + min(l, r)
# Runtime: 32 ms, faster than 73.08% of Python online submissions for Minimum Depth of Binary Tree.
# Memory Usage: 14.7 MB, less than 66.67% of Python online submissions for Minimum Depth of Binary Tree.


### 2. BFS 迭代

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
res = float('inf')
queue = [root]
nxt_last = last = root
level = 1
while queue:
node = queue.pop()
if not node.left and not node.right:
if level <= res:
return level
if node.left:
queue.insert(0, node.left)
nxt_last = node.left
if node.right:
queue.insert(0, node.right)
nxt_last = node.right
if node == last:
last = nxt_last
level += 1
# Runtime: 32 ms, faster than 73.08% of Python online submissions for Minimum Depth of Binary Tree.
# Memory Usage: 14.5 MB, less than 92.31% of Python online submissions for Minimum Depth of Binary Tree.


### 3. BFS 递归

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
self.res = float('inf')
self.bfs(root, 0, [])
return self.res
def bfs(self, root, level, lis):
if not root:
return
if not root.left and not root.right:
if self.res > level + 1:
self.res = level + 1
if level >= len(lis):
sub_lis = [root.val]
lis.append(sub_lis)
else:
lis[level].append(root)
self.bfs(root.left, level + 1, lis)
self.bfs(root.right, level + 1, lis)
# Runtime: 36 ms, faster than 45.93% of Python online submissions for Minimum Depth of Binary Tree.
# Memory Usage: 14.6 MB, less than 79.49% of Python online submissions for Minimum Depth of Binary Tree.