111_二叉树的最小深度

类型：树

• 111. 二叉树的最小深度 💚

  https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

  ❓ 求一棵树的最小深度。

  跟这一题是对着的：104. 二叉树的最大深度 💚

  💡 DFS

  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

  时间复杂度：O(n)，空间复杂度：O(n)

  💡 BFS

  当我们按层序遍历到第一个叶子结点时，直接返回当前的深度。

  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

  时间复杂度：O(n)，空间复杂度：O(n)