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

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

一、题目

1、算法题目

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

题目链接：

来源：力扣（LeetCode）

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

2、题目描述

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

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

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

代码语言：javascript复制

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

代码语言：javascript复制

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

二、解题

1、思路分析

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

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

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

2、代码实现

代码参考：

代码语言：javascript复制

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

        if (root.left == null &amp;&amp; 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;
    }
}