LeetCode 111 、二叉树的最小深度

一、题目描述

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

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

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

• 树中节点数的范围在 [0, 10^5] 内
• -1000 <= Node.val <= 1000

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
//  二叉树的最小深度（ LeetCode 111 ）:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
class Solution {
    public int minDepth(TreeNode root) {
        // 边界情况处理
        if (root == null) return 0;

        // 设置一个队列，用来存储二叉树中的元素
        Queue<TreeNode> nodeQueue = new LinkedList<>();

        // 队列添加二叉树的根节点
        nodeQueue.add(root);

        // 设置 depth 用来保存输出结果
        int depth = 0;

        // 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
        while (!nodeQueue.isEmpty()) {

            // 用来记录 queue 的长度，即每层节点的个数
            int size = nodeQueue.size();

            // 每到一层，深度就 +1
            depth++;

            // 使用 for 循环，将 nodeQueue 中的元素统计
            for (int i = 0; i < size; i++) {

                // 从 queue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点      
                TreeNode curNode = nodeQueue.poll();

                // curNode.left == null && curNode.right == null 
                // 说明是叶子结点
                // 由于【最小深度是从根节点到最近叶子节点的最短路径上的节点数量】
                // 直接返回 depth 
                if(curNode.left == null && curNode.right == null){
                    return depth;
                }

                // 判断当前节点的左子节点是否有值，如果有，则添加到 nodeQueue 中
                if (curNode.left != null){
                    nodeQueue.add(curNode.left);
                } 

                // 判断当前节点的右子节点是否有值，如果有，则添加到 nodeQueue 中    
                if (curNode.right != null){
                    nodeQueue.add(curNode.right);
                }

            }
        }

        // 返回 depth
        return depth;
    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www->algomooc->com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
//  二叉树的最小深度（ LeetCode 111 ）:https://leetcode-cn->com/problems/minimum-depth-of-binary-tree/
class Solution {
public:
    int minDepth(TreeNode* root) {
        // 边界情况处理
        if(root == NULL) return 0;

        // 设置一个队列，用来存储二叉树中的元素

        queue<TreeNode *> nodeQueue ;

        // 队列添加二叉树的根节点
        nodeQueue.push(root);

        // 设置 depth 用来保存输出结果
        int depth = 0;

        // 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
        while (!nodeQueue.empty()) {

            // 用来记录 queue 的长度，即每层节点的个数
            int size =  nodeQueue.size();

            // 每到一层，深度就 +1
            depth++;

            // 使用 for 循环，将 nodeQueue 中的元素统计
            for (int i = 0 ; i < size ; i++) {

                // 从 queue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点      
                TreeNode *curNode = nodeQueue.front();

                nodeQueue.pop();

                // curNode->left == NULL && curNode->right == NULL 
                // 说明是叶子结点
                // 由于【最小深度是从根节点到最近叶子节点的最短路径上的节点数量】
                // 直接返回 depth 
                if(curNode->left == NULL && curNode->right == NULL){
                   return depth;
                }

                // 判断当前节点的左子节点是否有值，如果有，则添加到 nodeQueue 中
                if (curNode->left != NULL){
                   nodeQueue.push(curNode->left);
                } 

                // 判断当前节点的右子节点是否有值，如果有，则添加到 nodeQueue 中    
                if (curNode->right != NULL){
                   nodeQueue.push(curNode->right);
                }

            }
        }

        // 返回 depth
        return depth;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
#  二叉树的最小深度（ LeetCode 111 ）:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        # 边界情况处理
        if root == None :
          return 0

        # 设置一个队列，用来存储二叉树中的元素
        nodeQueue = deque()

        # 队列添加二叉树的根节点
        nodeQueue.append(root)
        
        # 设置 depth 用来保存输出结果
        depth = 0

        # 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
        while nodeQueue : 

            # 用来记录 queue 的长度，即每层节点的个数
            size =  len(nodeQueue)

            # 每到一层，深度就 +1
            depth += 1

            # 使用 for 循环，将 nodeQueue 中的元素统计
            for i in range(size):

                # 从 queue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点      
                curNode = nodeQueue.popleft()

                # curNode.left == None && curNode.right == None 
                # 说明是叶子结点
                # 由于【最小深度是从根节点到最近叶子节点的最短路径上的节点数量】
                # 直接返回 depth 
                if curNode.left == None and curNode.right == None :
                   return depth
                

                # 判断当前节点的左子节点是否有值，如果有，则添加到 nodeQueue 中
                if curNode.left : 
                   nodeQueue.append(curNode.left)
                

                # 判断当前节点的右子节点是否有值，如果有，则添加到 nodeQueue 中    
                if curNode.right :
                   nodeQueue.append(curNode.right)


        # 返回 depth
        return depth