• Time:O(n)
• Space:O(h)

## C++

``````class Solution {
public:
int minDepth(TreeNode* root) {
if (!root)
return 0;
if (!root->left)
return minDepth(root->right) + 1;
if (!root->right)
return minDepth(root->left) + 1;
return min(minDepth(root->left), minDepth(root->right)) + 1;
}
};
``````

## JAVA

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

## Python

``````class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
if not root.left:
return self.minDepth(root.right) + 1
if not root.right:
return self.minDepth(root.left) + 1
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
``````

• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
int minDepth(TreeNode* root) {
if (!root)
return 0;

int ans = 0;
queue<TreeNode*> q{{root}};

while (!q.empty()) {
++ans;
for (int sz = q.size(); sz > 0; --sz) {
TreeNode* node = q.front();
q.pop();
if (!node->left && !node->right)
return ans;
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
}

throw;
}
};
``````

## JAVA

``````class Solution {
public int minDepth(TreeNode root) {
if (root == null)
return 0;

int ans = 0;
Queue<TreeNode> q = new ArrayDeque<>(Arrays.asList(root));

while (!q.isEmpty()) {
++ans;
for (int sz = q.size(); sz > 0; --sz) {
TreeNode node = q.poll();
if (node.left == null && node.right == null)
return ans;
if (node.left != null)
q.offer(node.left);
if (node.right != null)
q.offer(node.right);
}
}

throw new IllegalArgumentException();
}
}
``````

## Python

``````class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0

ans = 0
q = deque([root])

while q:
ans += 1
for _ in range(len(q)):
node = q.popleft()
if not node.left and not node.right:
return ans
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
``````