12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061 |
- /*
- * @Description:
- * @Version: 1.0
- * @Autor: zhuyijun
- * @Date: 2021-11-13 16:39:27
- * @LastEditTime: 2021-11-14 15:11:24
- */
- /*
- 给定一个二叉树,找出其最小深度。
- 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
- 说明:叶子节点是指没有子节点的节点。
- 示例 1:
- 输入:root = [3,9,20,null,null,15,7]
- 输出:2
- 示例 2:
- 输入:root = [2,null,3,null,4,null,5,null,6]
- 输出:5
- */
- #include <bits/stdc++.h>
- using namespace std;
- struct TreeNode {
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode() : val(0), left(nullptr), right(nullptr) {}
- TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- TreeNode(int x, TreeNode *left, TreeNode *right)
- : val(x), left(left), right(right) {}
- };
- int minDepth(TreeNode *root) {
- if (root == nullptr) {
- return 0;
- }
- queue<TreeNode> q;
- q.push(*root);
- int depth = 1;
- while (!q.empty()) {
- int sz = q.size();
- for (int i = 0; i < sz; i++) {
- //获取队列第一位元素
- TreeNode cur = q.front();
- //移除队列中第一位元素
- q.pop();
- if (cur.left == nullptr && cur.right == nullptr) {
- return depth;
- }
- if (cur.left != nullptr) {
- q.push(*cur.left);
- }
- if (cur.right != nullptr) {
- q.push(*cur.right);
- }
- }
- depth++;
- }
- return depth;
- }
- int main() { return 0; }
|