Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

二叉树的最小深度-111 #54

Open
sl1673495 opened this issue Jun 5, 2020 · 0 comments
Open

二叉树的最小深度-111 #54

sl1673495 opened this issue Jun 5, 2020 · 0 comments
Labels
BFS 广度优先遍历 DFS 深度优先遍历 二叉树

Comments

@sl1673495
Copy link
Owner

sl1673495 commented Jun 5, 2020

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)
      }
    }
  }
}
@sl1673495 sl1673495 added BFS 广度优先遍历 DFS 深度优先遍历 二叉树 labels Jun 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
BFS 广度优先遍历 DFS 深度优先遍历 二叉树
Projects
None yet
Development

No branches or pull requests

1 participant