111.二叉树的最小深度

题目#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))
}

优化后的代码解释

求二叉树的深度可分情况讨论

• 二叉树为空，返回最小深度为0if (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))
  通过这种递归方式避免了重复计算