[leetcode]minimum-depth-of-binar

问题：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 binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int run(TreeNode root) {
       if(root==null) return 0;
        int left=run(root.left);
        int right=run(root.right);
        if(left==0&&right==0) return 1;
        if(left==0) left=Integer.MAX_VALUE;
        if(right==0) right=Integer.MAX_VALUE;
        return Math.min(left,right)+1;
    }
}

第二种方法：使用广度优先遍历，使用arraylist存储每一层的节点，当遇到一层的节点没有子节点时返回最小深度

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int run(TreeNode root) {
        if(root == null) return 0;  
        ArrayList<TreeNode> last = new ArrayList<TreeNode>();  
        last.add(root);  
        int count =1;  
        while(!last.isEmpty()){  
            ArrayList<TreeNode> cur = new ArrayList<TreeNode>();  
            for (TreeNode treeNode : last) {  
                if(treeNode.left == null && treeNode.right == null) return count;  
                if(treeNode.left != null) cur.add(treeNode.left);  
                if(treeNode.right != null) cur.add(treeNode.right);  
            }  
            count++;  
            last = new ArrayList<TreeNode>(cur);  
        }  
        return count;  
    }
}