LeetCode 111（二叉树的最小深度）

解题步骤

1. 求最小深度考虑使用广度优先遍历，虽然深度优先遍历可以获取到所有节点的最大深度，然后在通过判断求出最小深度，但是性能消耗很大，需要把所有节点都遍历一次。
2. 在广度优先遍历过程中，记录每个节点的层级，如果遇到叶子节点则停止遍历，返回节点层级

通过广度优先遍历实现

• 时间复杂度：最坏情况 O (n)

• 空间复杂度：最坏情况 O (n)

  function minDepth(root) {
    if (!root) return 0;
    const q = [[root, 1]];
    while (q.length) {
        const [n, l] = q.shift();
        if (!n.left && !n.right) return l;
        if (n.left) q.push([n.left, l + 1]);
        if (n.right) q.push([n.right, l + 1]);
    }
  }

上方代码中存在一个循环，最坏的情况下是遍历了每一个节点，所以时间复杂度是 O (n)。代码中存在一个队列 q 最坏情况下也是存储了所有的节点，所以空间复杂度也是 O (n)。