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.

很简单,用recursive的方法,
特殊情况,如果root有一个child是null,因为root本身不能算是leaf,所以要单独处理,只看单独另一边的child


/**
 * 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;
        else if (root.left == null && root.right == null)
        {
            return 1;
        }
        else if (root.left == null)
        {
            return minDepth(root.right) + 1;
        }
        else if (root.right == null)
        {
            return minDepth(root.left) + 1;
        }
        else 
        {
            return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
        }
    }
}

Simpler code, notice that if we have a null for left or right for the root, we look at the other branch. This is a special condition that we can not return 0.

/**
 * 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;
        if (root.left == null && root.right == null)
            return 1;
        int left = Integer.MAX_VALUE;
        int right = Integer.MAX_VALUE;
        if (root.left != null)
            left = minDepth(root.left) + 1;
        if (root.right != null)
            right = minDepth(root.right) + 1;
        return Math.min(left, right);
    }
}

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