# LeetCode111. Minimum Depth of Binary Tree（二叉树 / 搜索）

## LeetCode111. Minimum Depth of Binary Tree（链表 / 搜索）

• Easy
• Accepted：275,214
• Submissions：789,211

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.

### 链接

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

### 题解

• 使用dfs，对当前结点，如果它的左子树为空，那么就得考虑它的右子树；如果它的右子树为空，那么就得考虑它的左子树，如果都不为空，那么就取左右子树深度的最小值。因为如果恰好有一个子树为空，那么当前结点就不是叶子节点，而深度只能从非空子树中产生。
• 使用bfs，层次遍历，对于当前结点，如果其左子树和右子树都为空，那么直接返回就行了。
• 实际上使用bfs比较好，考虑一颗二叉树，如果它的左子树有100个结点，右子树只有1个结点，那么使用dfs需要遍历101个结点而bfs只需要遍历2个结点。

### 代码

• Runtime: 16 ms, faster than 99.78% of C++ online submissions for Minimum Depth of Binary Tree.
• Memory Usage: 19.8 MB, less than 58.91% of C++ online submissions for Minimum Depth of Binary Tree.
// dfs

class Solution {
public:
int minDepth(TreeNode* root) {
if (root == NULL)
return 0;
int leftMinDepth = minDepth(root->left);
int rightMinDepth = minDepth(root->right);
return (leftMinDepth == 0 || rightMinDepth == 0) ?
leftMinDepth + rightMinDepth + 1 : min(leftMinDepth, rightMinDepth) + 1;
}
};
• Runtime: 16 ms, faster than 99.78% of C++ online submissions for Minimum Depth of Binary Tree.
• Memory Usage: 19.6 MB, less than 73.09% of C++ online submissions for Minimum Depth of Binary Tree.
// bfs

class Solution {
public:
int minDepth(TreeNode* root) {
if (root == NULL)
return 0;
queue <TreeNode* >q;
q.push(root);
int ans = 0;
while (!q.empty())
{
++ans;
int n = q.size();
for (int i = 0; i < n; ++i)
{
TreeNode* p = q.front();
q.pop();
if (p->left == NULL && p->right == NULL)
return ans;
if (p->left != NULL)
q.push(p->left);
if (p->right != NULL)
q.push(p->right);
}
}
return 0; // can not reach
}
};

### 参考

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

The end.
2019年3月7日 星期四