111. Minimum Depth of Binary Tree

Problem Statement

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

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.

Note: A leaf is a node with no children.

Example:

Input: root = [3,9,20,null,null,15,7] Output: 2

Input: root = [2,null,3,null,4,null,5,null,6] Output: 5

Solution Approach1

The minimum depth of a binary tree can be determined by recursively traversing the tree using Depth-First Search (DFS).

Solution Approach2

The minimum depth of a binary tree can be efficiently found using Breadth-First Search (BFS), stopping when the first leaf node is encountered.

Algorithm 1

1. If the current node (root) is None, return 0 as it’s a null node.
2. For leaf nodes (nodes with no left and right child), return 1.
3. Recursively compute the depth for the left and right subtree. If one of them is absent, return the depth of the other subtree + 1; otherwise, return the minimum depth between them + 1.

   Algorithm 2

4. Initialize a queue with the root node and an associated depth of 1.
5. Dequeue a node and check if it’s a leaf node (has no children); if so, return its associated depth.
6. Otherwise, enqueue its left and/or right child nodes with an incremented depth.

Implement

    class Solution:
      def minDepth(self, root: Optional[TreeNode]) -> int:
          if root == None:
              return 0
          if not root.left and not root.right:
              return 1
          left = self.minDepth(root.left)
          right = self.minDepth(root.right)
          if root.left and not root.right:
              return left + 1
          if root.right and not root.left:
              return right + 1
          return min(left, right) + 1

      def minDepth2(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        stack = [(root, 1)]
        while stack:
            node, step = stack.pop(0)
            if not node.left and not node.right:
                return step
            if node.left:
                stack.append((node.left, step + 1))
            if node.right:
                stack.append((node.right, step + 1))

    
    

Twitter  facebook  Email