Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/111.html

111	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.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its minimum depth = 2.

@tag-tree

Algorithm

DFS

The pitfall is, if a node has a child on the left and a null on the right, how to deal with it. In this case, the node is not a leaf, and we must continue to look for it. This time, we directly judge the root situation. Divided into left and right, or only left and right, return directly.

• First, it is judged to be empty. If the current node does not exist, return 0 directly.
• Then see if the left child node does not exist, then call the recursive function on the right child node and add 1 to return.
• Similarly, if the right child node does not exist, call the recursive function on the left child node and add 1 to return.
• If both left and right child nodes exist, call the recursive function on the left and right child nodes respectively, and return the smaller value of the two by adding 1

BFS

BFS traversal, recording the number of layers traversed, once the first leaf node is traversed, the current number of layers is returned, which is the minimum depth of the binary tree, if (!node->left && !node->right) return ans;.

Code

Java

• Java
• C++
• Python

• public class Minimum_Depth_of_Binary_Tree {
  
  	/**
  	 * Definition for a binary tree node.
  	 * public class TreeNode {
  	 *     int val;
  	 *     TreeNode left;
  	 *     TreeNode right;
  	 *     TreeNode(int x) { val = x; }
  	 * }
  	 */
  
  	// @note: key is how to handle null child node
      public class Solution_recursion {
  
          public int minDepth(TreeNode root) {
              if (root == null) {
                  return 0;
              }
  
              if (root.left == null && root.right == null) {
                  return 1; // leaf
              }
  
              if (root.left == null) {
                  return 1 + minDepth(root.right);
              }
  
              if (root.right == null) {
                  return 1 + minDepth(root.left);
              }
  
              return 1 + Math.min(minDepth(root.left), minDepth(root.right));
  
          }
      }
  }
  

• // OJ: https://leetcode.com/problems/minimum-depth-of-binary-tree/
  // Time: O(N)
  // Space: O(N)
  class Solution {
  public:
      int minDepth(TreeNode* root) {
          if (!root) return 0;
          queue<TreeNode*> q;
          q.push(root);
          int ans = 1;
          while (q.size()) {
              int cnt = q.size();
              while (cnt--) {
                  auto node = q.front();
                  q.pop();
                  if (!node->left && !node->right) return ans;
                  if (node->left) q.push(node->left);
                  if (node->right) q.push(node->right);
              }
              ++ans;
          }
          return -1;
      }
  };
  

• # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  class Solution:
      def minDepth(self, root: Optional[TreeNode]) -> int:
          if root is None:
              return 0
          if root.left is None:
              return 1 + self.minDepth(root.right)
          if root.right is None:
              return 1 + self.minDepth(root.left)
          return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
  
  ############
  
  # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  class Solution:
      def minDepth(self, root: Optional[TreeNode]) -> int:
          if root is None:
              return 0
          if root.left is None:
              return 1 + self.minDepth(root.right)
          if root.right is None:
              return 1 + self.minDepth(root.left)
          return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
  
  ##########
  
  # 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
      left = self.minDepth(root.left)
      right = self.minDepth(root.right)
      if not left and not right:
        return 1
      elif not left:
        return right + 1
      elif not right:
        return left + 1
      else:
        return min(left, right) + 1
  
  

All Problems

All Solutions