JS算法专题 - 树的层序遍历
发布网友
发布时间：2022-11-30 06:36
共1个回答
热心网友
时间：2023-11-01 08:32
102. 二叉树的层序遍历
107. 二叉树的层序遍历 II
429. N 叉树的层序遍历
这一类的题目，被归纳在leetcode的 广度优先搜索 标签下
这一类的题目，总结起来可以套用模板来解决，我们需要借用一下数据结构的知识：
队列 ：先进先出，后进后出
在JavaScript中，我们会使用 数组Array 来模拟队列：
先初始化一个 二叉树
先看看102的题目
解题：
从以上例子，只要步骤是：
有一个细节要注意：
这里用的是 pop() 和 unshift() ，是因为队列先进先出的特点，pop()从最后面弹出一个元素，unshift()把新元素放到最前面。 push() 和 shift() 搭配也有相同效果。
107的题目稍微改变了一下，要求输出是[[15,7], [9,20], [3]]，可以看出，就是把102的从上到下输出每一层节点，改成从下到上输出，首先想到的就是把102的数组反转就可以了。
但是，我们可能直接在保存结果数组的时候处理一下：
102中，我们使用 push() 把每一层的节点放入结果数组
107中，结果数组和102的反转了，所以，我们可以把 push() 改成 unshift() 即可，最后得到的结果就是，树的要节点那层在结果数组的最后，叶子节点在最前面。
429题中把二叉树改成了N叉树，树的结构发生了变化
但是可以看到，和二叉树的数据结构相比，就是把left和right合成children，那么在我们的模板中，也只需要修改一下
改成
这样就可以得到结果了。
想一下，如果再改一下：如何从右到左遍历每一层节点？层数是单数时从左到右，层数是双数时从右到左？
再扩展一下，这个算法能做什么呢？
当我们玩游戏，特别是走迷宫之类的游戏，是不是会从一个点出发，然后判断下一步能不能走，直到找出终点？BFS也是寻路方案的基础。
推荐一下leetcode上的总结：
二叉树层序遍历登场：我要打十个！
