二叉树的最小深度-111

[sl1673495]

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

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

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

示例:

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度  2.

思路

DFS

记录一个最小值 min，每当 DFS 到节点既没有左节点也没有右节点，就更新这个 min 值，整个树遍历完成后返回这个 min 即可。

let minDepth = function (root) {
  let min = Infinity
  let helper = (node, depth) => {
    if (!node) return
    if (!node.left && !node.right) {
      min = Math.min(min, depth)
      return
    }
    if (node.left) {
      helper(node.left, depth + 1)
    }
    if (node.right) {
      helper(node.right, depth + 1)
    }
  }
  helper(root, 1)

  return min === Infinity ? 0 : min
}

BFS

这题用 BFS 可能可以更快的找到答案，因为 DFS 必须要遍历完整棵树才可以确定结果，但是 BFS 的话由于层级是从低到高慢慢增加的遍历，所以发现某一层的某个节点既没有左节点又没有右节点的话，就可以直接返回当前的层级作为答案了。

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

  let depth = 0
  let queue = [root]

  while (queue.length) {
    depth++
    let len = queue.length
    while (len--) {
      let node = queue.shift()

      let left = node.left
      let right = node.right
      if (!left && !right) {
        return depth
      }

      if (left) {
        queue.push(left)
      }
      if (right) {
        queue.push(right)
      }
    }
  }
}