leetcode-111.png

计算二叉树的最小深度

BFS 一般使用队列来实现，将每个节点相邻的字节点都放入队列之中进行遍历
再将字节点的下一级的节点放入队列进行遍历

BFS

var minDepth = function (root) {
    if (!root) {
        return 0
    }
    let depth = 1
    let queue = []
    queue.push(root)
    while (queue.length) {
        // 这里需要一层一层的进行遍历，所以要将值写死
        // 不能动态的在for循环中用queue.length
        // 不然depth就不能正确的自增了
        let size = queue.length
        for (let i = 0; i < size; ++i) {
            let node = queue.shift()
            // 检测到左右节点都为空的时候，那就是最小深度了
            if (!node.left && !node.right) {
                return depth
            }
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        depth++
    }
    return depth
};

DFS

var minDepth = function (root) {
    if (!root) {
        return 0
    }
    // 左节点为空，递归右节点
    if(!root.left){
        return minDepth(root.right) + 1
    }
    // 右节点为空，递归左节点
    if(!root.right){
        return minDepth(root.left) + 1
    }
    // 两个节点都不为空那就两个节点都递归，并且选出其中最小的一个
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1
};