111. 二叉树的最小深度

111.二叉树的最小深度

解题思路

用BFS

JavaScript解法代码

var minDepth = function(root) {
    if(!root) return 0

    let q = []
    q.push(root)
    let depth = 1
    while(q.length > 0){
        let size = q.length
        for(let i=0;i<size;i++){
            let cur = q.shift()
            if(cur.left === null && cur.right === null){
                return depth
            }
            if(cur.left != null){
                q.push(cur.left)
            }
            if(cur.right != null){
                q.push(cur.right)
            }
        }
        
        depth++
    }
    return depth
};

总结：

BFS模板：

function bfs(graph, startNode, targetNode) {
  // 创建一个队列，并将起始节点加入其中
  let queue = [];
  queue.push(startNode);
  
  // 创建一个 set 来存储已访问过的节点
  let visited = new Set();
  visited.add(startNode);
  
  // 当队列非空时，继续搜索
  while (queue.length > 0) {
    // 从队列的前面移除一个节点
    let currentNode = queue.shift();
    
    // 检查是否到达了目标节点
    if (currentNode === targetNode) {
      return true; // 或者做一些其他操作
    }
    
    // 将当前节点的所有未访问过的邻居节点加入队列，并标记为已访问
    let neighbors = graph[currentNode];
    for (let neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        queue.push(neighbor);
        visited.add(neighbor);
      }
    }
  }
  
  // 如果执行到这里，说明没有找到从 startNode 到 targetNode 的路径
  return false;
}