Day124 | 灵神 | 二叉树 | 二叉树最小深度

111.二叉树最小深度

111. 二叉树的最小深度 - 力扣（LeetCode）

思路：

之前都是递归写法，这次写层序遍历

就是我们找到的第一个叶子节点，它的深度就是树的最小的深度

完整代码：

层序遍历：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==nullptr)
            return 0;
        queue<TreeNode*> q;
        int depth=0;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                TreeNode *t=q.front();
                q.pop();
                if(t->left==nullptr&&t->right==nullptr)
                    return depth+1;
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
            depth++;
        }
        return depth;      
    }   
};

递归代码：

class Solution {
public:
    int get_depth(TreeNode *t)
    {
        if(t==nullptr)
            return 0;
        if(t->left==nullptr)
            return get_depth(t->right)+1;
        if(t->right==nullptr)  
            return get_depth(t->left)+1;
        return min(get_depth(t->left),get_depth(t->right))+1;
    }
    int minDepth(TreeNode* root) {
        return get_depth(root);        
    }   
};