版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
- minimum depth of binary tree
<p>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.</p>
- 题目大意：给定一颗二叉树，找到它的最小深度。最小深度指的是，从根节点到最近的叶子节点，沿着这条路径走过的节点的数目。
- 思路：利用队列采用层序遍历，一旦找到一个叶节点，它肯定是最短的。
- 代码：
class Solution
{
public:
typedef TreeNode* tree;
int run(TreeNode *root)
{
// 层序遍历，一旦找到一个叶节点，它肯定是最短的
if (root == NULL)return 0;
queue<tree> qu;
tree now = root; // 记录该层的当前节点
tree last = root; // 记录该层的最后一个节点
int level = 1;
int size = 0;
qu.push(root);
while (!qu.empty())
{
now = qu.front(); // 取队首
qu.pop(); // 出队首
size = qu.size();
if (now->left != NULL)qu.push(now->left);
if (now->right != NULL)qu.push(now->right);
// 没有元素进队，说明这是一个叶子节点，找到的第一个叶子节点为最短的
if (size - qu.size() == 0)break;
// last==now，说明当前节点走到了该层的最后一个节点
if (last == now)
{
level++;
// last指向下一层的最后一个节点
if (!qu.empty())last = qu.back();
}
}
return level;
}
};
- 测试结果：
- 以上。
版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
