Leetcode–Minimum Depth of Binary Tree

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

Notes:

  1. Basic question, similar to Maximum Depth of Binary Tree.

Java Solution


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if(root== null) return 0;
        return getMin(root, 1);
    }
    private int getMin(TreeNode root, int depth){
        if(root.left== null &&  root.right==null)
            return depth;
        int left=Integer.MAX_VALUE;
        int right = Integer.MAX_VALUE;
        if(root.left!= null)
            left = getMin(root.left, depth+1);
        if(root.right!= null)
            right = getMin(root.right, depth+1);
        
        return Math.min(left , right);
    }
}

Java Solution II

Actually it can be simpler than the above solution, since it does not pass in and out the depth, only one way will do. Be careful about cases that have left/right subtree empty.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if(root== null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if(left==0 && right== 0) return 1;
        else if(left==0 || right ==0) return Math.max(left, right)+1;
        else return Math.min(left, right)+1;
    }
    
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s