Lexi's Leetcode solutions

[leetcode] Minimum Depth of Binary Tree | 二叉树的最小深度

Posted on: August 1, 2013

尼玛这破题居然跑了好几遍才对!

一开始错的方法:

public int minDepth(TreeNode root) {
  if (root == null)
    return 0;
  int left = minDepth(root.left);
  int right = minDepth(root.right);
  return Math.min(left, right) + 1;
}

比如a#b这种左子树为空的树,我直接认为左子树的depth为0了,那当然左子树的depth小,然后parent直接取了0+1。问题在于,某个子树是null的时候,它不是叶子节点啊!这个时候就算没形成一个叶子到root的path,则认为depth为正无穷。改进:

public int minDepth(TreeNode root) {
  if (root == null)
    return Intger.MAX_VALUE;
  if (root.left == null && root.right == null)
    return 1; //说明是个leaf了!
  int left = minDepth(root.left);
  int right = minDepth(root.right);
  return Math.min(left, right) + 1;
}

忍不住回忆为啥做maxdepth的时候就没遇见问题呢?(如下)因为求的是max,所以那种某个子树为0的情况就被Math.max给解决了。总之这种题最好做完了试一试,一试就能立刻看出毛病了,自己干想还真想不到。

public int maxDepth(TreeNode root) {
  if (root == null)
    return 0;
  int left = maxDepth(root.left);
  int right = maxDepth(root.right);
  return Math.max(left, right) + 1;
}
Advertisements
Tags: ,

3 Responses to "[leetcode] Minimum Depth of Binary Tree | 二叉树的最小深度"

你这如果给个空树给你,不就在
if (root == null)
return Intger.MAX_VALUE;
返了个最大值出来么?还是我看错了?

第一句话就是“一开始错的方法“

这种做法的话给个空树,层数久违MAX_VALUE了,不过可能没有这种测试数据吧

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: