☆打卡算法☆LeetCode 111、二叉树的最小深度 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

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

题目链接：

来源：力扣（LeetCode）

链接： 111. 二叉树的最小深度

2、题目描述

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

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

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

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

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

二、解题

1、思路分析

这道题首先想到的就是深度优先搜索的方法，遍历整棵树，找出最小深度。

对于每一个非根节点，只需要分别计算左右子树的最小子节点深度。

也就是把大问题转化为小问题，那么这个问题就可以递归解决。

2、代码实现

代码参考：

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }
}

3、时间复杂度

时间复杂度 ： O(N)

其中N是树的节点数，对每个节点只访问一次。

空间复杂度： O(H)

其中H是树的高度，空间复杂度主要取决于递归时的开销，递归的空间复杂度为O(N)，平均情况下树的高度与节点数的对数正相关，空间复杂度为O(log N)，总的时间复杂度就是O(H)。

三、总结

这道题用了广度优先搜索方法，同样，也可以使用广度优先搜索的方法去遍历整棵树。

对于这道题来书，广度优先搜索方法可以保证最先搜索到的叶子节点的深度一定最小。