题目#111.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树[3,9,20,null,null,15,7],
返回它的最小深度 2.
题目分析
题目想要问的是深度，所以能表示深度的节点是没有子节点的，我们只要关注二叉树中没有子节点的节点，然后找到最小深度就可以了，很容易想到使用深度优先搜索的方式，通过函数参数，给每个节点绑定一个深度值，然后使用全局变量去所有节点的最小深度即可，代码如下
代码
private var t = Int.MAX_VALUE
fun minDepth(root: TreeNode?): Int {
if (root == null) return 0
dfs(root, 1)
return t
}
private fun dfs(root: TreeNode, level: Int) {
if (root.left == null && root.right == null) {
t = t.coerceAtMost(level) // 取最小
return
}
if (root.left != null) {
dfs(root.left!!, level + 1)
}
if (root.right != null) {
dfs(root.right!!, level + 1)
}
}
代码解释
使用深度优先搜索遍历整个二叉树，每个二叉树节点都有对应的level值，代表着节点的深度，节点的深度只在没有子节点的使用有效，所以深度优先搜索使用if (root.left == null && root.right == null)进行剪枝，去除不满足的节点，这里还用到了kotlin中的Int的扩展方法coerceAtMost，它能够拿到两个值中的最小值，当然，你想使用Math.min，或是kotlin.math.min都是可以的。
代码优化
可以看出，当我们在使用深度优先搜索的时候，我已经遍历完了root，我还要再遍历一遍root.left，root.right，如此递归下去，极大的增加了时间复杂度，这种问题属于我们经常犯的却难以发现的问题，那我们如何改进它呢？下面给出了优化的代码
优化后的代码
fun minDepth(root: TreeNode?): Int {
if (root == null) return 0
if (root.left == null && root.right != null) return 1 + minDepth(root.right)
if (root.left != null && root.right == null) return 1 + minDepth(root.left)
return 1 + minDepth(root.left).coerceAtMost(minDepth(root.right))
}
优化后的代码解释
求二叉树的深度可分情况讨论
- 二叉树为空，返回最小深度为0
if (root == null) return 0 - 二叉树子节点有且仅有一个为空，返回不为空的子节点的最小深度加一
if (root.left == null && root.right != null) return 1 + minDepth(root.right)
if (root.left != null && root.right == null) return 1 + minDepth(root.left) - 二叉树子节点都不为空，返回两个子节点的最小深度的最小值加一
return 1 + minDepth(root.left).coerceAtMost(minDepth(root.right))
通过这种递归方式避免了重复计算
