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.

Solution1: recursion
如果一个节点只有左子树或者右子树，不能取它左右子树中小的作为深度，因为那样会是0。只有在叶子节点才能判断深度。
Run time complexity is O(n), stack space since it's recursion.

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

Solution2: iterative
相当于BFS。找到第一个叶子节点就返回。
Run time complexity is O(n), space complexity is O(n).

/**
 * 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;
        
        LinkedList queue = new LinkedList();
        int curNum = 0;
        int lastNum = 1;
        int level = 1;
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur.left == null && cur.right == null) {  //找到第一个叶子节点就返回
                return level;
            }
            lastNum--;
            if(cur.left != null) {
                queue.offer(cur.left);
                curNum++;
            }
            if(cur.right != null) {
                queue.offer(cur.right);
                curNum++;
            }
            if(lastNum == 0) {
                lastNum = curNum;
                curNum = 0;
                level++;
            }
        }
        return level;
    }
}