题解 | #二叉树的最小深度#
合并回文子串
http://www.nowcoder.com/practice/2f43728b46744546b4ad7f4f0398054f
广度优先搜索计算二叉树最小深度
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
private:
int next_layer_num=0; //计算二叉树下一层的节点数
int current_layer_num=1; //当前遍历层剩余待处理的节点数
int deep_min=1; //最小深度
queue <struct TreeNode*> q; //队列,记录遍历中间结果
public:
/**
*
* @param root TreeNode类
* @return int整型
*/
int run(TreeNode* root) {
if(root == NULL) return 0;
q.push(root);
do{
struct TreeNode * node = q.front();
if(node->left){
++next_layer_num;
q.push(node->left);
}
if(node->right){
++next_layer_num;
q.push(node->right);
}
//只有为叶子节点才返回
if(node->left==NULL && node->right==NULL)
return deep_min;
q.pop();
// current_layer_num==0表示当前层已经遍历结束
if(--current_layer_num==0)
{
//下一层要遍历的节点数
current_layer_num=next_layer_num;
next_layer_num=0;
//深度加一
++deep_min;
}
}while(!q.empty());
return 0;
}
};