Aug 3 2017 Update
遞歸方法1：
private 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;
int min = Math.min(minDepth(root.left), minDepth(root.right));
return min + 1;
}
樹只有一個孩子的情況要去遞歸執(zhí)行它的孩子能颁，depth要+1挚币。
最后那個int min也要+1, 因為還要把根結(jié)點算上砚著。
遞歸方法2：
感覺比1難懂一點滑肉。旋圆。其實一樣。
public int minDepth(TreeNode root) {
if(root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0)
?left + right + 1
: Math.min(left,right) + 1;
}
--
原來的post
遞歸方法通用只需要3行。
非遞歸方法：
public int minDepth(TreeNode root) {
if (root == null) return 0;
int level = 0;
int curNum = 1;
int nextNum = 0;
LinkedList<TreeNode> linkedList = new LinkedList<>();
linkedList.add(root);
while (!linkedList.isEmpty()) {
TreeNode node = linkedList.poll();
curNum--;
if (node.left == null && node.right == null)
return level + 1;
if (node.left != null) {
linkedList.add(node.left);
nextNum++;
}
if (node.right != null) {
linkedList.add(node.right);
nextNum++;
}
if (curNum == 0) {
curNum = nextNum;
nextNum = 0;
level++;
}
}
return level;
}
