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.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        /*
        //Solution 1: Iteration
        if (root == null) {
            return 0;
        }
        
        LinkedList<TreeNode> node = new LinkedList<>();
        LinkedList<Integer> counter = new LinkedList<>();
        
        node.add(root);
        counter.add(1);
        
        while (!node.isEmpty()) {
            
            TreeNode cur = node.poll();
            int count = counter.poll();
            
            if (cur.left == null && cur.right == null) {
                return count;
            }
            // Do not need to use if... else
            if (cur.right != null) {
                node.add(cur.right);
                counter.add(count + 1);
            }
            
            if (cur.left != null) {
                node.add(cur.left);
                counter.add(count + 1);
            }
        }
        
        // Must have return value here
        return 0;
        */
/*
Or         LinkedList<Integer> counters = new LinkedList<>();
        nodes.add(root);
        counters.add(0);
        
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.remove();
            int count = counters.remove();
            
            if (node == null) {
                return count;
            }
            if (root.right != null) {
                nodes.add(node.right);
                counters.add(count + 1);
            }
            if (root.left != null) {
                nodes.add(node.right);
                counters.add(count + 1);
            }
            
        }
        return 0;
*/
        
        //Solution 2: Recursion, simple
        
        if (root == null) {
            return 0;
        }
        
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }
        
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }
        
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
        
        /*
        //Solution 3: Recursion, with helper
        if (root == null) {
            return 0;
        }
        
        return helper(root);
    }
    
    private int helper(TreeNode root) {
        
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        
        if (root.left == null && root.right == null) {
            return 1;
        }
        
        return Math.min(helper(root.left), helper(root.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