111.二叉树的最小深度

111. 二叉树的最小深度 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

题目描述：

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

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

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

示例 1：

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

示例 2：

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

题目分析：

按照上一篇文章中所写的求二叉树的最大深度对的解法，这道题应该不难。

后序递归解法：

采用比较容易理解的后续递归及递归三部曲可以得到如下代码：

1. 递归第一步：确定递归函数的参数和返回值

参数为要传入的二叉树根节点，返回的是int类型的深度。

代码如下：

int getDepth(TreeNode* node)

2. 递归第二步：确定终止条件 

终止条件也是遇到空节点返回0，表示当前节点的高度为0。

代码如下：

if (node == NULL) return 0;

3. 递归第三步：确定单层递归的逻辑 

这块和求最大深度可就不一样了，一些同学可能会写如下代码：

int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
int result = 1 + min(leftDepth, rightDepth);  //关键问题出在这一步
return result;

 对于左右子树均存在时，上述代码没有问题。但是当子树不存在时，由前两步getDepth（）得到的深度会存在0，如下图所示：

回顾一下题目所给的最小深度的定义：

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是到最近的叶子节点，即没有左右子节点的叶子节点。

那么刚刚所写的单层递归逻辑的代码中是没有判断是否为叶子节点的功能的：

int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
int result = 1 + min(leftDepth, rightDepth);  //关键问题出在这一步
return result;

补救措施就是在得到leftDepth和rightDepth之后，要判断一下左右子树的存在情况。

• 如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
• 反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
• 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

 代码如下：

int leftDepth = getDepth(node->left);           // 左
int rightDepth = getDepth(node->right);         // 右
                                                // 中
// 当一个左子树为空，右不为空，这时并不是最低点
if (node->left == NULL && node->right != NULL) { 
    return 1 + rightDepth;
}   
// 当一个右子树为空，左不为空，这时并不是最低点
if (node->left != NULL && node->right == NULL) { 
    return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;

整体代码如下：

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);           // 左
        int rightDepth = getDepth(node->right);         // 右
                                                        // 中
        // 当一个左子树为空，右不为空，这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空，左不为空，这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }

    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

上述代码是写了一个专门的getDepth函数进行递归，也可以不写，直接在力扣提供的函数minDepth上进行递归，如下所示：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        //左
        int leftDepth = minDepth(root->left);
        //右
        int rightDepth = minDepth(root->right);

        if(root->left == nullptr && root->right != nullptr) 
            return rightDepth + 1;

        if(root->left != nullptr && root->right == nullptr)
            return leftDepth + 1;
        
        int result = min(leftDepth, rightDepth) + 1;
        return result;

    }
};

注意，上面两个写法中的result = min(leftDepth, rightDepth) + 1; 这行代码即包含了左右子树均存在的情况，还包含了左右子树均不存在的情况。均存在时，就去最小值加1；均不存在时，leftDepth和rightDepth均为0，那么算上此时两个空子树的父节点那一层，result做了加1操作（可以想象整个二叉树只有一个根节点组成时的情形）。

所以，代码里的+1操作，就是在后序遍历中处理完了左右子树后，开始考虑子树对应的根节点计算深度（左右中）。

层序遍历解法：

在二叉树层序遍历文章的基础上来实现最小深度的求解，关键一点就是第一次遍历到某个节点的左右孩子都为空的时候，说明遍历到最低点了，此时应该直接return depth，程序运行结束。如果其中一个孩子不为空则不是最低点。

代码如下：

class Solution {
public:
    //层序遍历
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int depth = 0;
        while(!que.empty())
        {
            int size = que.size();
            depth++;
            for(int i = 0; i < size; ++i)
            {
                TreeNode*  node = que.front();
                que.pop();
                //最低处判断放这里也行
                // if(node->left == nullptr && node->right == nullptr)
                //     return depth;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
                if(node->left == nullptr && node->right == nullptr)
                    return depth;               
            }
        }
        return depth;

    }
};