[LeetCode] 111. Minimum Depth of Binary Tree

Posted on | In

Problem

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:

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

1
2
3
4
5
    3
   / \
  9  20
    /  \
   15   7

return its minimum depth = 2.

Explanation

  1. First, we check if the root node is empty, if it is empty, then return 0.
  2. If the root node doesn’t have left and right child, then return 1.
  3. If the root node only has right child, then we return 1 plus the min length of the right subtree.
  4. If the root node only has left child, then we return 1 plus the min length of the left subtree.
  5. If the root node has both left and right child, then we return 1 plus the minimum of min length left subtree and min length of the right subtree.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        else if (root.left == null && root.right == null) return 1;
        else if (root.left == null) return 1+minDepth(root.right);
        else if (root.right == null) return 1+minDepth(root.left);
        else return 1+Math.min(minDepth(root.left), minDepth(root.right));
    }
}