leetcode【二叉树—简单】111.二叉树的最小深度

文章目录

• 前言
• 题目
• 题解
• NO1：递归
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为二叉树专题。

---

题目

题目来源leetcode

leetcode地址：111. 二叉树的最小深度，难度：简单。

题目描述(摘自leetcode)：

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

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

示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
 
提示：
树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000

本地调试：

class Solution {

    public int minDepth(TreeNode root) {
        ...
    }
}

class Main {
    public static void main(String[] args) {
        // 构建树
        Integer[] nums = new Integer[] { 2,null,3,null,4,null,5,null,6 };
        TreeNode root = buildTree(nums);
        System.out.println(new Solution().minDepth(root));
    }

    //根据数组来构建二叉树
    public static TreeNode buildTree(Integer[] nums) {
        Deque<TreeNode> queue = new LinkedList();
        TreeNode root = new TreeNode(nums[0]);
        queue.add(root);
        for (int i = 1; i < nums.length; i += 2) {
            TreeNode parentNode = queue.poll();
            if (nums[i] != null) {
                TreeNode leftNode = new TreeNode(nums[i]);
                queue.offer(leftNode);
                parentNode.left = leftNode;
            } else {
                parentNode.left = null;
            }
            if (i + 1 < nums.length && nums[i + 1] != null) {
                TreeNode rightNode = new TreeNode(nums[i+1]);
                queue.offer(rightNode);
                parentNode.right = rightNode;
            } else {
                parentNode.right = null;
            }
        }
        return root;
    }

}

---

题解

NO1：递归

思路： 抓住这里的细节，这里的二叉树最小深度指的是从根节点到最近叶子节点的最短路径上的节点数量。也就是说不是叶子节点的就要进行额外处理，这里我们只需要在递归方法中进行对应情况匹配即可。

代码：

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 获取到左右节点
    int leftDeeps = minDepth(root.left);
    int rightDeeps = minDepth(root.right);

    // 情况1：左孩子为空，右孩子不为空
    if (root.left == null && root.right != null) {
        return rightDeeps + 1;
    } else if (root.left != null && root.right == null) {// 情况2：左孩子不为空，右孩子为空
        return leftDeeps + 1;
    }

    // 左右孩子都为空（叶子节点，左右为0,0）、左右孩子都不为空（通过比对递归得到的左右孩子的深度取最小深度值）
    return 1 + Math.min(leftDeeps, rightDeeps);
}

---

参考文章

[1]. leetcode题解

[2]. 代码随想录—二叉树的最小深度

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.9