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

Posted by: lexigrey on: August 1, 2013

• In: leetcode
• 3 Comments

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

一开始错的方法：

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;
}

Tags: easy, tree