Leetcode # 111. Minimum Depth of Binary Tree

Problem

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

Solution

Time Complexity: O(len(tree))
Space Complexity: O(max_depth(tree))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def minDepth(self, root: Optional[TreeNode]) -> int:
    if root is None: return 0
    
    min_depth = inf
    stack = [(root, 1)]
    while stack:
      curr, depth = stack.pop()
      # ... some process about target
      if curr.left is None and curr.right is None:
        min_depth = min(depth, min_depth)
        continue
      if depth >= min_depth: continue
          
      for child in [curr.left, curr.right]:
        if child:
          stack.append((child, depth + 1))
    return min_depth

Last Updated on 2024/04/20 by A1go