zhangdizhangdi

111.二叉树的最小深度

题目

LeetCode 简单

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

示例：
输入：root = [3,9,20,null,null,15,7]
输出：3

方法：广度优先

BFS 队列 O(n) O(height)

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

  let queue = [[root, 1]]
  while (queue.length) {
    const [node, depth] = queue.shift() as [TreeNode, number]

    console.log('node', node.val, 'depth', depth)

    if (!node.left && !node.right) {
      return depth
    }
    if (node.left) queue.push([node.left, depth + 1])
    if (node.right) queue.push([node.right, depth + 1])
  }
}

const tree = new Tree([3, 9, 20, 8, null, 15, 7])
console.log('🌰', minDepth(tree.root))

方法：深度优先【todo⌛️】