🥉Easy

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

返回它的最小深度 2.

题解

深度优先搜索

对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。

Python

  1. class Solution:
  2.     def minDepth(self, root: TreeNode) -> int:
  3.         if not root:
  4.             return 0
  6.         if not root.left and not root.right:
  7.             return 1
  9.         min_depth = 10**9
  10.         if root.left:
  11.             min_depth = min(self.minDepth(root.left), min_depth)
  12.         if root.right:
  13.             min_depth = min(self.minDepth(root.right), min_depth)
  15.         return min_depth + 1

广度优先搜索

当我们找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。

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