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.

Code

Java

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));

        }
    }
}

All Problems

All Solutions