题解 | #二叉树的最小深度#

合并回文子串

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;
    }
};
全部评论

相关推荐

喜欢走神的孤勇者练习时长两年半:爱华,信华,等华,黑华
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务