LeetCode111.二叉树的最小深度

题目

思路

虽然看起来和上次的104有一点类似，but...不可混为一旦勒！！！坑多多的！

1.最小深度不能直接左右取小，因为单边子树会让 0 被当成最短路径。所以先判空

2.再单独处理叶子、只有左孩子、只有右孩子这三种情况，只有两边都非空时才用 min 取小，每层加 1 递归返回。（有左没右，有右没左主要是要防止一根棍那种特例！如下图这种）

代码

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==nullptr)return 0;
        //没左没右
        if(root->right==nullptr&&root->left==nullptr)
        return 1;
        //有左没右
        if(root->right==nullptr&&root->left!=nullptr)
        return 1+minDepth(root->left);
        //没左有右
         if(root->right!=nullptr&&root->left==nullptr)
         return 1+minDepth(root->right);
        //有左有右
        if(root->right!=nullptr&&root->left!=nullptr)
        return min(minDepth(root->right),minDepth(root->left))+1;

        return 0;
    }
};

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2603_96571045/article/details/170347418