{% tabs %} {% tab title="Python" %}
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root: return 0
ans = 1
q = collections.deque()
q.append(root)
while q:
len_q = len(q)
for i in range(len_q):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
elif not node.left and not node.right :
return ans
ans += 1
{% endtab %}
{% tab title="recursive" %}
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root: return 0
left = self.minDepth(root.left)
right = self.minDepth(root.right)
if left == 0 or right == 0: # 并不是都没有儿子
return left + right + 1
return min(left, right) + 1
{% endtab %} {% endtabs %}