算法练习11：二叉树的最小深度(leetcode 111)

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

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

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

深度优先算法（前序遍历）解法

1. 使用中序遍历出所有路径，并记录出它的深度；
2. 比较所有路径的深度，输出最小路径

// 深度优先算法（前序遍历）：返回树的最小深度
var minDepth = function(root) {
  if(!root) return;
  // 记录最小深度
  let min = 0;
  // 记录当前路径的深度
  let curNum = 0;
  // 判断是不是已经有了第一条完整路径
  let hasOnePath = false;
  function dps(root) {
      if(!root) return;
      // 遍历到当前节点，路径+1
      curNum += 1;
      // 再遍历当前节点的左右子节点
      dps(root.left)
      dps(root.right)
      // 如果当前节点是叶子节点，就记录其深度
      if(!root.left && !root.right) {
          console.log(root);
          // 如果不是第1条路径，就比较当前路径是不是最短路径，是就更新其为最短路径
          if(hasOnePath) {
              if(curNum < min) {
                  min = curNum
              }
          // 如果是第一条路径，将最小路径设为这条路径的深度，作为比较的初始值
          }else {
              min = curNum
              hasOnePath = true
          }
      }
      // 当回溯到其父节点时，深度要-1
      curNum -= 1;
  }
  dps(root)
  return min;
};

广度优先遍历

因为广度优先遍历是一层一层遍历的，当它遍历到的第一个叶子节点，就是最短节点路径

// 广度优先算法：返回树的最小深度
var minDepth2 = function(root) {
  if(!root) return 0;
  let queue = []
  // 将当前节点和它的层级数一起保存到队列中
  queue.push([root, 1])
  let curNode = null;
  let dept = 0;
  // 只要队列不为空，就继续
  while(queue.length) {
    // 拿出队列中最早的节点
    [curNode, dept] = queue.shift()
    // 如果这个节点是叶子节点，说明这就是第一个最短路径的节点
    if(!curNode.left && !curNode.right) {
      return dept;
    }
    // 如果不是叶子节点，就遍历它的左右节点，将其放入队列中
    if(curNode.left) {
      queue.push([curNode.left, dept + 1])
    }
    if(curNode.right) {
      queue.push([curNode.right, dept + 1])
    }
  }
};