写点什么

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

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

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


解题思路:


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

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

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

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

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

  6. 每遍历一层,就记录当前的层数,完成所有节点的遍历时,就得到了二叉树的最大深度。


/** * 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 maxDepth = 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();
// 如果子节点存在,则将子节点入队,作为下一层的节点 node.left && queue.push(node.left); node.right && queue.push(node.right); }
// 遍历完一层之后,层数加1 level++; }
// 由于每次都会遍历一层,当完成二叉树遍历时,最后的层数就是最大深度 return level;};
复制代码


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

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

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