1、描述

111给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

3 / 9 20 / 15 7 返回它的最小深度 2.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、关键字

树，深度，最小

3、思路

树的层序遍历

4、note

1、图的广度优先就是树的层序遍历的推广 3、广度优先遍历的代码结构第一层while()判断是否为空，第二层while()判断 一层是否结束 2、queueSTL不熟悉， queue入队，如例：q.push(x); 将x 接到队列的末端。

queue出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。

访问queue队首元素，如例：q.front()，即最早被压入队列的元素。

访问queue队尾元素，如例：q.back()，即最后被压入队列的元素。

判断queue队列空，如例：q.empty()，当队列空时，返回true。

访问队列中的元素个数，如例：q.size()

5、复杂度

时间 O(N2）平方 空间O(n)

6、code

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; 广度优先是树的层次遍历的推广 */ class Solution { public: int minDepth(TreeNode* root) { queue<TreeNode*>qu; // 树的队列 if(root==NULL) return 0; // 如果根节点为空，直接返回 qu.push(root); int res=1; // 记录结果 while(!qu.empty()) // 不为空 { int queNum=qu.size(); // 一层的数量 while(queNum--) // 此一层的操作 { auto tem=qu.front(); // 取此一层队列的第一个元素 if(tem->left==NULL) // 判断左子树是否为空，此条件下两种情况，后边else有两种情况 { //qu.push(tem->left); if(tem->right==NULL) // 如果右子树也是空，即为叶子节点 return res; else // 右子树不为空 qu.push(tem->right); } else // 左子树不为空 { qu.push(tem->left); // 左子树直接进队列 if(tem->right!=NULL) // 判断右子树也得不为空才进队列 qu.push(tem->right); } qu.pop(); // 此为队列删除队首元素 } res++; } return res; } };