問題：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;
}
}
第二種方法：使用廣度優(yōu)先遍歷憾儒，使用arraylist存儲每一層的節(jié)點糟港，當遇到一層的節(jié)點沒有子節(jié)點時返回最小深度
/**
* 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;
}
}
