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.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
2018/0813 update: 不能直接用l or r, 因为我们要先选小的, 如果小的是空, 然后才需要去判断那个大的. 所以需要min 及max, 而且min应该在前面.
思路为DFS recursive, 但是需要注意的是, 比如[1,2] 应该return 2, 但是上面知会return 1. 所以需要return min(l,r) or max(l, r), 因为有一边有, 另一边没有的时候要返回有的.
2020/0509 update: 直接用BFS,碰到第一个leaf,return当时的height即可。
1. Constraints
1) can be none => 0
2. Ideas
BFS T: O(n) S: O(n)
DFS recursive T: O(n) S: O(n)
3, Code
class Solution:
def minDepth(self, root):
if not root: return 0
l, r = self.minDepth(root.left), self.minDepth(root.right)
return 1+ (min(l, r) or max(l, r))
=> more elegant
class Solution:
def minDepth(self, root):
if not root: return 0
d = map(self.minDepth, (root.left, root.right))
return 1 + (min(d) or max(d))
利用BFS
class Solution:
def miniDepth(self, root):
if not root: return 0
queue = collections.deque([(root, 1)])
while queue:
node, height = queue.popleft()
if not node.left and not node.right:
return height
if node.left:
queue.append((node.left, height + 1))
if node.right:
queue.append((node.right, height + 1))
4. Test cases
1) [1,2]
2) [3,9,20,null,null,15,7]