二叉树的最小深度二叉树的最小深度

版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~

minimum depth of binary tree

【二叉树的最小深度】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.

题目大意：给定一颗二叉树，找到它的最小深度。最小深度指的是，从根节点到最近的叶子节点，沿着这条路径走过的节点的数目。
思路：利用队列采用层序遍历，一旦找到一个叶节点，它肯定是最短的。
代码：

class Solution { public: typedef TreeNode* tree; int run(TreeNode *root) { // 层序遍历，一旦找到一个叶节点，它肯定是最短的 if (root == NULL)return 0; queue 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; } };