111 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

题解

利用层序遍历， 当节点没有左子树也没有右子树时， 那就是最小深度，直接返回。

var minDepth = function(root) {
    const queue = []
    var result = 0
    if(!root) {
        return result
    }
    queue.push(root)
    while(queue.length) {
        const size = queue.length
        result++
        for(let i=0;i<size;i++) {
            const current = queue.shift()

            if(current !== root) {
                // 左右节点都为空
                if(!current.left && !current.right) {
                    return result
                }
            }
            if(current.left) {
                queue.push(current.left)
            }
            if(current.right) {
                queue.push(current.right)
            }
        }
    }
    return result
};

递归解法

和最大深度一样，利用后序遍历，唯一的不一样是处理的步骤

var minDepth = function(root) {
    if(!root) return 0

    const minDepthLeft = minDepth(root.left)
    const minDepthRight = minDepth(root.right)

    if (!root.left && root.right) {
        //左节点为空，右节点不为空
        return 1 + minDepthRight
    }
    if (root.left && !root.right) {
        return 1 + minDepthLeft
    }

    return Math.min(minDepthLeft, minDepthRight) + 1
}