题号：111. 二叉树的最小深度
题目描述：
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明: 叶子节点是指没有子节点的节点。
示例1: 给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
示例2: 给定二叉树 [1,2,null],
1
/
2
返回它的最小深度 2.
优化前：深度优先搜索
遍历整棵树，记录最小深度。对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。
func minDepth(root *TreeNode) int { if root == nil { return 0 } ans := 0 if root.Left == nil && root.Right == nil { return 1 } else if root.Left != nil && root.Right != nil{ ans = min(minDepth1(root.Left), minDepth1(root.Right)) + 1 }else if root.Left != nil{ ans = minDepth1(root.Left) + 1 }else if root.Right != nil{ ans = minDepth1(root.Right) + 1 } return ans } func min(a, b int) int { if a > b { return b } return a }
优化后：
func minDepth(root *TreeNode) int { if root == nil { return 0 } if root.Left == nil && root.Right == nil { return 1 } minSum := math.MaxInt32 if root.Left !=nil{ minSum = min(minDepth(root.Left),minSum) } if root.Right !=nil{ minSum = min(minDepth(root.Right),minSum) } return minSum+1 }
复杂度分析：
- 时间复杂度：O(N)O(N)，其中 NN 是树的节点数。对每个节点访问一次。
- 空间复杂度：O(H)O(H)，其中 HH 是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为 O(N)O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(\log N)O(logN)。
