一、题目
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)。
三、总结
这道题用了广度优先搜索方法，同样，也可以使用广度优先搜索的方法去遍历整棵树。
对于这道题来书，广度优先搜索方法可以保证最先搜索到的叶子节点的深度一定最小。
