[刷题笔记] minimum depth of binary tree

题目

https://leetcode.com/problems/minimum-depth-of-binary-tree/submissions/

思路

这个题目标榜的难度是easy，然而通过率只有39%到底是为什么呢？

第一遍的答案

def min_depth(root)
  if root.left == nil && root.right == nil
    return 1
  end
  left_min = min_depth(root.left)
  right_min = min_depth(root.right)
  return left_min > right_min ? 1+right_min : 1+left_min
end

Exception. 没有处理root是nil的情况。

第二遍，加上处理

def min_depth(root)
  return 0 unless root
  if root.left == nil && root.right == nil
    return 1
  end
  left_min = min_depth(root.left)
  right_min = min_depth(root.right)
  return left_min > right_min ? 1+right_min : 1+left_min
end

Wrong answer.

testCase: 
[2,null,3,null,4,null,5,null,6]

actual: 1
expected: 5

如果只有左右中的一个child的情况，一个child深度为0，另一个child深度为计算的值，这个时候不能认为0是正确的深度，因为只有当左右都为nil的时候才是我们获取深度的时候。

最终结果

def min_depth(root)
  return 0 unless root
  if root.left == nil && root.right == nil
    return 1
  elsif root.left == nil
    return 1 + min_depth(root.right)
  elsif root.right == nil
    return 1 + min_depth(root.left)
  end
  left_min = min_depth(root.left)
  right_min = min_depth(root.right)
  return left_min > right_min ? 1+right_min : 1+left_min
end