102 .二叉树层序遍历-力扣(LeetCode )发布： 2021年7月30日16:09:20
问题的说明和例子举出二叉树。 请返回按层序扫描得到的节点值。 也就是说，对于每个层次，从左到右访问所有节点。
示例：
二叉树： [3、9、20、空、空、15、7]、
返回该层序遍历的结果：
[
[3]、
[ 9，20 ]，
[ 15，7 ]
]
解答我的问题我的问题1 (用前序遍历树和深度记录深度)在成功前的尝试中看到这个问题时，我脑海中第一个联想到的是之前学到的广度优先遍历(Breadth First Search，简称： BFS ) 我隐约记得BFS是在说图中扫描部分的内容。 当然二叉树也可以看成是特殊的图啊。 当然也可以应用BFS。 但是，我有点不记得有关的细节。 于是又马上产生了别的想法。 也就是说，只要将当前扫描节点所在层次的深度用变量depth存储，将深度相同的节点存储到相同的数组中，最后将在各个层次获得的结果存储到result中，并将result作为结果返回即可。 这几天，我刚做过回溯相关的主题，脑子里很快就出现了应用回溯思想来维持深度的大致想法。 所以我首先写了以下程序。
//结果错误，也不知道错误的详细情况，所以varlevelorder=function(root ) ) { let depth=-1； //level表示let level=[]，用于动态存储某个层次的节点； //result为最终结果let result=[]； 预跟踪(根)； 返回结果； 功能预览(节点) if (！ 节点() { depth； //level.pop (； //console.log('Depth '，depth )； level.push(node.val； //console.log )、level )； result[depth]=level； //console.log('result '，result )； 预跟踪(node.left )； 深度- -； pretraverse(node.right )； 深度- -； }； }； 想法很棒，但很遗憾，执行的结果非常奇怪
(2) [阵列(5)5]，阵列(5)，- 1:阵列(5)5)，- 2:阵列(5)5) [ 3，9，20，15，7 ] 1: ] ) 7 )-1:(5) [3、9、20、15、7]Length:3初步判断深度未维护，同时level也未随深度变化及时改变。 于是我开始修改上述代码。 在此期间，它用于调试代码，但LeetCode的相关功能需要费用。 没办法。 我还以为能不能自己实现根据节点数组序列构造树的函数。 写了一部分后，我突然觉得可能有人写了关联函数，搜索后找到了一个符合我要求的树函数，现在就可以在本地调试了。 以后碰到二叉树的主题，也不用在脑子里想象。 主要参考以下博客：
更新： 2021年7月30日01:34:37
参考： leetcode使用javascript通过数组创建树_Niap的博客-CSDN博客
参考： LeetCode二叉树如何构建，一维数组直接构建完整二叉树(遵循LeetCode格式) _USTC灰尘博客-CSDN博客
参考： LeetCode是一个基于主题输入生成树_两个橘子树博客-CSDN博客
感谢您分享以上博客。 我是直接使用的JavaScript实现的那个函数(上面的第一个参考)。
现在有本地调试，所以我们开始逐步观察代码的执行。 在此期间，费了很多力气，过程也不详细说明。 最终成功解决了我手下的第一个问题。
首先遍历树并在depth中记录深度(成功提交)的区别在于，将depth从全局变量更改为首先遍历的函数preTraverse ()的参数。 这样，可以将深度和结果值指定给下一级别的递归，并临时动态存储某个级别的节点值，而无需遍历level。 (具体原理很难解释，有意研究者总体思路还是和我最初尝试的一样，详细可以看到以下注释。
/* * definitionforabinarytreenode.* function treenode (val，left，right ) * this.val===undefined？ 0: val (* this.left=(left===undefined？ nu
ll : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number[][]} */var levelOrder = function (root) { // result存储最终结果，注意result是作为一个二维数组返回的 let result = []; // depth初始化为0，防止result[0]的结果为undefined preTraverse(root, 0, result); return result; // 前序遍历函数，depth用于记录当前节点的深度变化，同时也作为result数组的下标 // 也可将depth理解为当前节点node的深度，下面的res是形参，注意不要和上面的result搞混了 function preTraverse(node, depth, res) { // 如果当前节点为空，则结束一层递归 if (!node) { return; } // 因为depth也要作为res的下标，res的长度是根据depth值的增长而同步增加的， // 如果depth增长至超出了res的长度，则说明树的遍历进入了下一层了， // 此时res数组就要再填入一个空数组用来存储新的一层的节点值了 if (depth >= res.length) { res.push([]); } // 注意res[depth]也是一个数组哦 res[depth].push(node.val); // 递归遍历当前节点node的左右子节点，此前的操作其实都可以抽象为对当前节点的访问 // 因为要往下遍历子节点了，所以要记得要将depth+1作为下一层遍历的depth值 // 注意下面的res值，这里为什么不像之前做的题那样做一个深拷贝再传入呢？值得推敲 preTraverse(node.left, depth + 1, res); preTraverse(node.right, depth + 1, res); }};提交记录34 / 34 个通过测试用例状态：通过执行用时：68 ms, 在所有 JavaScript 提交中击败了97.22%的用户内存消耗：39.6 MB, 在所有 JavaScript 提交中击败了37.74%的用户时间：2021/07/30 16:13可以看到这种解法的空间性能表现不怎么好，毕竟是用到了递归嘛。当然其实也有非递归方式的前序遍历，空间性能应该会好一点，但此处就先不做研究了。
更新：2021年7月30日17:40:05
在我写上面的depth解法的过程中，我发现该题的评论区102. 二叉树的层序遍历 - 力扣（LeetCode）有一位题友【@宝宝可乖了】的思路和我上面的一模一样，代码的结构自然也很相似，我觉得他的那种写法更加的简洁优雅，所以就将上面的代码修改了一小部分。感谢这位题友的评论分享。
【更新结束】
我的题解2（BFS层序遍历树）更新：2021年10月18日17:47:23
这段时间也陆续做了好几道层序遍历（BFS）的题目，我觉得都可以用本篇博客中的这种思路，稍作转变即可，有些题就是在本题的基础上稍微改一两行代码就可以了。详情可以看下方【有关参考】部分的整理。
【更新结束】
在看上面说到的评论区时，我也看到有题友说上面那种解法属于凑巧型，是LeetCode的测试用例集有bug才刚好通过，我倒不这么认为，因为无论是层序遍历还是先序遍历，总归是要逐个访问每一个节点的。上面的解法中只是用先序遍历的手法访问了所有的节点，然后在访问每个节点时通过观察我们所维护的depth变量来达到分辨当前层的效果，并将同一层的节点值放入对应下标为depth的result数组中，最后的结果还是存储在全局变量result中的（当然这里的全局并不是我们平常接触的全局哈，而是相对内部函数preTraverse()来说的，这里是为了方便表达）。所以说这样的方法只是用先序遍历的手法达到我们想要的层序遍历的结果而已，也是合理的。
那么既然题目都说了这题目的名字都提示我们用层序遍历完成这道题目，那就研究一下层序遍历如何操作吧。
更新：2021年7月30日19:41:32
吃了个饭回来继续。首先，在二叉树的层序遍历中，我们需要一个辅助队列结构queue来存储当前遍历节点，队列结构先进先出的特点正好可以满足我们广度优先搜索要求（而在深度遍历中，我们一般使用具有先进后出特点的栈结构来做辅助）。详解请看下方注释。
注意，我们说queue是存储当前遍历节点，但是千万不要以为queue中只会存储下面代码中所说的当前层中的节点 ，因为for循环在遍历当前层的所有节点时。也会将被我们所弹出的队首节点的左右子节点（如果子节点不为空的话）压入queue，所以queue是不断变化的。这也是为什么for循环中的i的结束条件我不是写成i < queue.length，而是先将queue.length的值存起来，就是为了防止不断变化的queue.length不会影响我们对某一层节点的遍历。
其实一开始我没有在意for循环中的i的结束条件是否被写成i < queue.length会给程序带来什么影响，我会写成len = queue.length; i < len;只是因为我习惯这样写，因为我觉得这样的话，在判断结束条件时，就不用每次都重新计算一遍数组的length值了，多少会快一点。事实上，这两种写法在一般情况下没有什么太大的区别，但在这里就比较关键了。我是看到【微信公众号：代码随想录】的博主写的相关资料中的代码注释里特意提到了这个i值的结束条件的问题，我才仔细思考了一下，发现确实不能简单地写成i<queue.length。
/** * 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 levelOrder = function (root) { let result = []; // 初始化queue为辅助队列，通过数组的push和shift方法的配合，可以实现队列先进先出的特点 let queue = []; // 先把根节点放入队列，否则后续的while循环将无法工作 queue.push(root); // 如果该树是一颗空树，那么直接返回空结果， // 不要漏掉这一步判断，否则无法通过所有LeetCode测试用例 if(root === null) { return result; } // 如果队列不为空，则说明还没有遍历完所有层，注意这个while循环是以层为单位迭代的 while (!!queue.length) { // level用于存储当前层的所有节点，所以每新进一层时都应该将其初始化为空数组 let level = []; // 这个for循环用于遍历当前层的所有节点，注意下面我为什么不直接写成 i<queue.length for (let i = 0, len = queue.length; i < len; i++) { // 弹出队首节点，但注意不要马上丢弃它，因为后面还用得上 let node = queue.shift(); // 将刚才弹出的节点值存入level level.push(node.val); // 下面两个if用于判断当刚才弹出的节点的左（右）子节点不为空时，则将子节点加入队尾 if (!!node.left) { queue.push(node.left); } if (!!node.right) { queue.push(node.right); } } // for循环结束则说明当前层的节点已经全部存入level中，已经获得了一个结果 result.push(level); } // while循环结束说明树中的所有层都已经遍历完，将结果返回 return result;};提交记录34 / 34 个通过测试用例状态：通过执行用时：72 ms, 在所有 JavaScript 提交中击败了93.51%的用户内存消耗：39.4 MB, 在所有 JavaScript 提交中击败了76.86%的用户时间：2021/07/30 19:35总的来说，就是让上面的while循环负责二叉树深度方向的遍历，而for循环则负责某一层中的广度方向的遍历。其中利用queue这个辅助队列先进先出的结构特点来确保逐层遍历的效果。
官方题解更新：2021年7月29日18:43:21
因为我考虑到著作权归属问题，所以【官方题解】部分我不再粘贴具体的代码了，可到下方的链接中查看。
更新：2021年7月30日16:16:21
参考：二叉树的层序遍历 - 二叉树的层序遍历 - 力扣（LeetCode）
【更新结束】
有关参考更新：2021年7月30日21:03:06
参考：【微信公众号：代码随想录 2020-09-25】二叉树：层序遍历登场！
参考：深度优先遍历(DFS)和广度优先遍历(BFS)_JeansPocket的博客-CSDN博客_广度优先遍历
参考：js二维数组定义和初始化的三种方法总结_javascript技巧_脚本之家
【我做的其他层序遍历题目】
更新：2021年10月18日17:51:40
参考：【算法-LeetCode】199. 二叉树的右视图（二叉树；层序遍历；BFS）_赖念安的博客-CSDN博客
参考：【算法-LeetCode】103. 二叉树的锯齿形层序遍历（二叉树；层序遍历；BFS）_赖念安的博客-CSDN博客
参考：【算法-LeetCode】429. N 叉树的层序遍历（N叉树；层序遍历；BFS）_赖念安的博客-CSDN博客