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

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

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示： 树中节点数的范围在 [0, 105] 内 -1000 <= Node.val <= 1000

  1. const minDepth = (root) => {
  2.   if (root == null) return 0;    // 递归到null节点，返回高度0
  4.   if (root.left && root.right) { // 左右子树都存在，当前节点的高度1+左右子树递归结果的较小值
  5.     return 1 + Math.min(minDepth(root.left), minDepth(root.right));
  6.   } else if (root.left) {        // 左子树存在，右子树不存在
  7.     return 1 + minDepth(root.left);
  8.   } else if (root.right) {       // 右子树存在，左子树不存在
  9.     return 1 + minDepth(root.right);
  10.   } else {                       // 左右子树都不存在，光是当前节点的高度1
  11.     return 1;
  12.   }
  13. };

BFS

  1. const minDepth = (root) => {
  2.   if (root == null) return 0;
  4.   const queue = [root]; // 根节点入列
  5.   let depth = 1;        // 当前层的深度
  7.   while (queue.length) { 
  8.     const levelSize = queue.length; // 当前层的节点个数
  9.     let i = 0
  10.     for (; i < levelSize; i++) {         // 遍历 逐个出列
  11.       const node = queue.shift();      // 出列
  12.       // 如果没有孩子，直接返回所在层数
  13.       if (node.left == null && node.right == null) { 
  14.         return depth;
  15.       }
  16.       if (node.left) queue.push(node.left); // 有孩子，让孩子入列
  17.       if (node.right) queue.push(node.right);
  18.     }
  19.     depth++; // 肯定有下一层，如果没有早就return了
  20.   }
  21. };