111. 二叉树的最小深度

[Geekhyt]

原题链接

递归 dfs

1. root 为空时，高度为 0
2. root 的左右子树都为空时，高度为 1
3. 如果左子树或者右子树为空时，返回另一棵子树的高度
4. 否则返回两棵子树的高度最小值

const minDepth = function(root) {
    if (root === null) return 0
    if (root.left === null && root.right === null) {
        return 1
    }
    if (root.left === null) {
        return 1 + minDepth(root.right)
    }
    if (root.right === null) {
        return 1 + minDepth(root.left)
    }
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1
}

• 时间复杂度：O(n)
• 空间复杂度：O(logn)