二叉树的最大or最小深度

二叉树的最大深度

LeetCode-104

// 层序遍历(BSF)解法
var maxDepth = function(root) {
  if(root === null) return 0
  let q = [root]
  let res = 0
  while(q.length) {
    res++ // 每迭代一次，深度+1
    let len = q.length
    for(let i = 0; i < len; i++) {
        let node = q.shift()
        if(node.left) q.push(node.left)
        if(node.right) q.push(node.right)
    }
  }
  return res
}

// 深度优先遍历(DFS)
var maxDepth = function(root) {
  if(root === null) return 0
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}

二叉树的最小深度

LeetCode-111

// 层序遍历(BSF)解法
var minDepth = function(root) {
  if(root === null) return 0
  let q = [root]
  let res = 0
  while(q.length) {
    res++
    let len = q.length
    for(let i = 0; i < len; i++) {
      let node = q.shift()
      // 左右子树都不存在 才能说明最小深度到底了
      if(!node.left && !node.right) return res
      if(node.left) q.push(node.left)
      if(node.right) q.push(node.right)
    }
  }
}