一、leetcode算法
1、二叉树的最小深度
1.1、题目
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
1.2、思路
思路一：此题和之前的找出最大的深度类似，只不过是判断条件改变一下，同样可以用深度优先搜索来解决。遍历整棵树，记录最小深度。对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。
1.3、答案
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; } }
复杂度分析
时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。
空间复杂度：O(H)，其中 H是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(logN)。
