111. 二叉树的最小深度

广度遍历

广度遍历下可以在第一次遇到叶子结点就终止

function minDepth(root: TreeNode | null): number {
  if (!root) {
    return 0
  }

  const stack = [root]
  let depth = 0

  while (stack.length) {
    depth += 1

    //遍历当前层
    const size = stack.length
    for (let i = 0; i < size; i += 1) {
      // 层序遍历使用 shift 从前取，避免拿错其他层的结点
      const currentRoot = stack.shift()

      // 因为是一层一层遍历
      // 所以第一次遇到的叶子结点，就是最小深度
      if (!currentRoot.left && !currentRoot.right) {
        return depth
      }

      if (currentRoot.left) {
        stack.push(currentRoot.left)
      }

      if (currentRoot.right) {
        stack.push(currentRoot.right)
      }
    }
  }
}

深度遍历

深度遍历需要全部遍历完才能确定结果，因为没有看完全部层，无法确定结果

function minDepth(root: TreeNode | null): number {
  if (!root) {
    return 0
  }

  let result

  function traverse(root: TreeNode, depth: number) {
    if (!root.left && !root.right) {
      // 如果没有初始化过深度，进行初始化
      if (!result) {
        result = depth
      } else {
        // 否则使用更小的
        result = Math.min(result, depth)
      }
    }

    if (root.left) {
      traverse(root.left, depth + 1)
    }

    if (root.right) {
      traverse(root.right, depth + 1)
    }
  }

  // 深度从 1 开始计算
  traverse(root, 1)

  return result
}