Leetcode 111. 二叉树的最小深

ccf19881030

发布于 2023-03-13 11:10:17

2040

发布于 2023-03-13 11:10:17

文章被收录于专栏：ccf19881030的博客ccf19881030的博客

力扣111- 二叉树的最小深度

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

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

说明：叶子节点是指没有子节点的节点。示例 1：

bin1.png

输入：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：BFS深度优先遍历

这道题有几种解法，可以使用BFS优先遍历的方法解决。用maxDepth表示二叉树的最小深度使用一个队列先保存上一次节点，最开始就是root根节点，然后将root方法一个空的队列中。当队列不为空时，依次从队首获取元素，然后将队首的元素的左右节点(如果不为空)加入队列中，再将队首元素弹出，这样循环往复，在弹出当前层节点的过程中，同时将下层节点放入队列中，此时二叉树的深度加1，如果当前队首元素的左右节点均为空，则返回maxDepth;

C++实现代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // BFS优先搜索求解
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        std::deque<TreeNode *> bfsDeque;

        int maxDepth = 1;   // 默认根节点为1层
        bfsDeque.push_back(root);

        while (!bfsDeque.empty()) {
            int szLen = bfsDeque.size();
            // 将当前队列中的所有节点向下扩散
            for (int i = 0; i < szLen; i++) {
                // 取出当前队列首元素
                TreeNode* frontNode = bfsDeque.front();
                bfsDeque.pop_front();
                // 判断是否到达终点
                if (frontNode->left == nullptr && frontNode->right == nullptr) {
                    return maxDepth;
                }
                // 将 frontNode 的左右节点加入队列
                if (frontNode->left != nullptr) {
                    bfsDeque.push_back(frontNode->left);
                }
                if (frontNode->right != nullptr) {
                    bfsDeque.push_back(frontNode->right);
                }
            }
            // 遍历完每一层元素，深度加1
            maxDepth++;
        }
        return maxDepth;
    }
};

解法2：递归法

同样也是递归法，主要就是确定单层的逻辑，和最大深度不一样的是，最小深度的条件限制比较多，如下图所示

test02.png

因此我们需要分类讨论，节点的孩子情况，因为这涉及到我们如何进行递归求解。 C++代码实现如下：

class Solution {
public:
    int GetMinDepth(TreeNode* root)
    {
        if(root==nullptr)
        {
            return 0;
        }
        int leftdepth = GetMinDepth(root->left);
        int rightdepth = GetMinDepth(root->right);
        // 假如只有左孩子 那么返回左孩子的深度
        if(root->left!=nullptr && root->right==nullptr)
        {
            return 1 + leftdepth;
        }
        // 假如只有右孩子返回右孩子的深度
        if(root->left==nullptr && root->right!=nullptr)
        {
            return 1 + rightdepth;
        }
        // 加一是为了加当前的根节点
        int depth = std::min(leftdepth, rightdepth) + 1;
        return depth;
    }
    int minDepth(TreeNode* root) {
        return  GetMinDepth(root);
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2023-03-10，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树