[LeetCode 111] Minimum Depth of Binary Tree

Question

link

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.

Stats

Frequency	1
Difficulty	1
Adjusted Difficulty	3
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

There are various ways to solve this question.

Eg. DFS, BFS, queue and so on.

Solution

I have nothing to say with the code.

Code

public int minDepth(TreeNode root) {
    if (root == null) return 0;
    return helper(root, Integer.MAX_VALUE, 1);
}

private int helper(TreeNode node, int min, int level) {
    if (node == null || level >= min)
        return min;
    if (node.left == null && node.right == null)
        return level;
    min = helper(node.left, min, level + 1);
    min = helper(node.right, min, level + 1);
    return min;
}

Updated on June 10th, this question is better solved with the Divide & Conquer template! link

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return checkLeaf(root);
}

private int checkLeaf(TreeNode node) {
    if (node == null) {
        return Integer.MAX_VALUE;
    }
    if (node.left == null && node.right == null) {
        return 1;
    }
    int ll = checkLeaf(node.left);
    int rr = checkLeaf(node.right);
    return 1 + Math.min(ll, rr);
}