题目描述：

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),

 

本文链接：http://bookshadow.com/weblog/2015/11/28/leetcode-minimum-depth-binary-tree/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码