题解 | #二叉树的最小深度#

function TreeNode(x) {
  this.val = x;
  this.left = null;
  this.right = null;
}

// 递归解法，相当于树的后序遍历，回溯到根节点时，比较左右子树的深度取最小+1就是整棵树的最小深度
function run(root) {
  if (undefined === root || null === root) {
    return 0
  }

  let leftChildDeep = run(root.left)
  let rightChildDeep = run(root.right)

  return (leftChildDeep < rightChildDeep) ? (leftChildDeep + 1) : rightChildDeep + 1
}

// 层次遍历解法，由于是从第一层开始遍历，遇到叶子直接返回叶子所在层次就是最小深度
function run(root) {
  if (undefined === root || null === root) {
    return 0
  }

  let queue = []

  root.level = 1
  queue.push(root)

  while (queue.length) {
    let node = queue.shift()

    // 放入左右孩子
    if (node.left) {
      node.left.level = node.level + 1
      queue.push(node.left)
    }
    if (node.right) {
      node.right.level = node.level + 1
      queue.push(node.right)
    }

    if ((!node.left) && (!node.right)) {
      return node.level
    }
  }

  return 0
}

let root = new TreeNode(1)
root.left = new TreeNode(2)
root.right = new TreeNode(3)
root.left.left = new TreeNode(4)
root.left.right = new TreeNode(5)

console.log(
  run(root)
)