## 题目描述：

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.

DFS或者BFS均可，详见代码。

## Python代码（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 root is None:
return 0
left = self.minDepth(root.left)
right = self.minDepth(root.right)
if left and right:
return min(left, right) + 1
return max(left, right) + 1
``````

## Python代码（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
queue = collections.deque([(root, 1)])
while queue:
node, step = queue.popleft()
if not node.left and not node.right:
return step
if node.left:
queue += (node.left, step + 1),
if node.right:
queue += (node.right, step + 1),
``````

Pingbacks已关闭。