写点什么

LeetCode 题解:111. 二叉树的最小深度,BFS,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 01 月 07 日
LeetCode题解:111. 二叉树的最小深度,BFS,JavaScript,详细注释

原题连接:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/


解题思路:


  1. 该题可以使用BFS,逐层遍历二叉树。

  2. 使用队列进行遍历,队列中按顺序存储了每一层的节点。

  3. 每次循环时,将队列中当前层的节点依次取出,即可在这次循环中,获取到当前层所有节点的值。

  4. 同时,将当前层每个节点的子节点,依次存入队列尾部,等待下一次遍历处理。

  5. 不断重复步骤 3、4,即可完成层序遍历。

  6. 左右子节点都不存在的节点,就是树的叶子节点。

  7. 每遍历一层,就记录当前的层数,当第一次遇到叶子节点时,意味着当前的深度就是最小的二叉树深度。


/** * Definition for a binary tree node. * function TreeNode(val, left, right) { *     this.val = (val===undefined ? 0 : val) *     this.left = (left===undefined ? null : left) *     this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number} */var minDepth = function (root) {  let queue = []; // 存储层序遍历结果  let level = 0; // 记录遍历的二叉树层级  root && queue.push(root); // 如果树存在,才进行遍历
// 不断遍历队列,直到队列为空时,完成树的层序遍历 while (queue.length) { // 缓存当前层的节点数量,避免队列操作过程中数量不断改变,对for循环次数造成影响 let queueLength = queue.length;
// 每次只遍历当前一层的节点 while (--queueLength >= 0) { // 将当前层的节点依次从队列取出 const node = queue.shift();
// 没有子节点的节点就是叶子节点 // 第一次遇到叶子节点时,当前深度就是最小二叉树深度 if (!node.left && !node.right) { // 由于当前深度还未记录,返回时需要加1 return level + 1; }
// 如果子节点存在,则将子节点入队,作为下一层的节点 node.left && queue.push(node.left); node.right && queue.push(node.right); }
// 遍历完一层之后,层数加1 level++; }
// 如果没有进入循环,当前深度为0 return level;};
复制代码


发布于: 2021 年 01 月 07 日阅读数: 16
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:111. 二叉树的最小深度,BFS,JavaScript,详细注释