本专题旨在分享刷 Leecode 过程发现的一些思路乏味或者有价值的题目。【当然是基于 js 进行解答】。
(这道题应该算是二叉树的根底题,倡议还是学一下,不难且经典)
题目相干
- 原题地址: https://leetcode-cn.com/probl…
-
题目形容:
从上到下按层打印二叉树,同一层的节点按从左到右的程序打印,每一层打印到一行,例如,给定二叉树:
[3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7
返回其档次遍历后果:
[[3], [9,20], [15,7] ]
Tips
思考某些同学可能比拟少用 js 来刷 leetcode,咱们在这里简略介绍下, 对于 树类型 的数据输出, 在 js 里的示意。形如上题中的内容,给定二叉树的输出,其实并非一个数组,而应该是如下所示: 每个节点是一个 object
const input = { val: 3, left: { // left 示意以后节点的左侧子节点 val: 9, left: null, // 对照上图能够看到 节点 9 没有左右子节点 right: null, }, right: { val: 20, left: { val: 15, // 对照上图能够看到 节点 15 没有左右子节点 left: null, right: null, }, right: { val: 7, // 对照上图能够看到 节点 7 没有左右子节点 left: null, right: null, }, } }
思路解析
这道题比拟根底,其实考的是BFS+ 层序遍历,怎么说呢?
首先 BFS(Breadth First Search)也就是 广度优先搜寻 , 指的是在遍历过程,每次总是优先遍历以后节点的所有 邻接节点,将其放入一个队列,比方上题的例子:
- step1: 首先筹备一个空队列(也就是数组)
[]
,并且把根节点放入数组中, 也就是[3]
; - step2: 先 取出 队列的最后面节点(此时队列只有节点 3,取出之后队列置空),而后把它的所有邻接节点(在二叉树外面也就是左右子节点)按程序 退出拜访队列,所以此时队列元素为
[9 20]
, - step3: 持续依照第二步的规定,取出节点 9,并把 9 的子节点放入队列(无子节点);再把节点 20 取出,并且把节点 20 的子节点存入队列,此时队列残余元素为
[15, 7]
; - step4: 持续依照第二步规定,取出 节点 15,并把子节点放入队列(无子节点);再把节点 7 取出,并且把节点 7 的子节点存入队列,此时队列残余元素为
[]
,队列为空 完结整个过程 ;
仔细观察以上的步骤,你发现了吗?
- 除了第一步初始化数据,后续的所有步骤 都在 依照第 2 步的规定反复;
-
察看每一步的取出后果:
- step2, 取出[3];
- step3, 取出[9, 20];
- step4, 取出[15, 17];
这里每一步的取出后果 正好就是题设要求的 每一层遍历的后果。
- 整个过程完结条件,就是 节点队列为空。
这道题讲到这里,其实大抵思路就曾经很清晰了,或者说,其实下面的步骤就曾经是伪代码了(没方法,因为题目自身就十分典型 -_-!)
- 首先第 2 步的规定必定就是主函数,因为它全程始终循环;
- 其次,初始条件 / 完结条件别离对应的是 根节点入队列 , 和队列为空;
- 惟一的难点,在于如何优雅地解决【分层输入】,而这一点 我倡议大家间接看我最初贴地残缺代码。
残缺代码
那么其实就能够间接看代码了:
var levelOrder = function(root) {if (!root) { // 如果根节点都不存在 那间接完结
return [];}
const nodes = [root]; // 初始化,对应后面剖析里地初始条件,const res = [];
while(nodes.length > 0) { // 外层循环 当节点队列为空时完结
const tempRes = [];
let isEmpty = false;
//【留神点】这个内循环 也就是解决分层输出地精华所在,大家能够认真琢磨下这个循环条件
// 尝试答复这里为什么不采纳“i=0;i<nodes.length;i++”的模式
for(let i = nodes.length;i > 0 ; i--) {const node = nodes.shift();
tempRes.push(node.val);
if(node.left) {nodes.push(node.left);
}
if(node.right) {nodes.push(node.right);
}
}
res.push(tempRes);
}
return res;
};
好了整体的题目算是根底题,就不画动态图了(画图很耗时),然而想两个问题给大家思考:
- 也就是代码块里的问题,为什么内循环的条件不是
i=0;i<nodes.length;i++
?如果是,会怎么样? - 如果本道题演变成输入深度优先遍历的后果,外围要点要怎么改变?
如果可能答复出下面的两个问题,那基本上就了解了这个知识点!