小余同学给讲的层次遍历
层序遍历就是从上到下 从左到右遍历二叉树 比如上面这颗 层序遍历就是 1 4 2 3 5
要实现层序遍历一般我们使用队列(why?因为先进先出,这和二叉树的访问结构对上了,某一层进入队列,可以先访问这一层的节点,再通过每个节点的左右孩子访问下一层,然后把对应节点出列)
Leetcode里面的代码其实就是给定你数据结构的定义,你只要能了解就可以用
其实是这样的
Struct Node{
Int val;
Node left;
Node right;
}
Root也是Node类型是给定的二叉树的根 二叉树的结构已经通过left和right定义好 比如上面root.left(也是一个Node型变量)代表它的左孩子,root.left.val 代表左孩子的结点的值是4,root.right.val=2
传入函数的是根结点
1 | var levelOrderBottom = function(root) { |
通过上面的二叉树模拟一下:
开始 queue 里面是 1节点 level是0,,res为空
当queue.length(1)不为0循环:
Temp置空
走for遍历这一层的节点;
将 1节点放入res[level]队列 (level为0)
看看他的左右孩子是否存在,依次进入temp队列 此时temp是 4和2节点
第一层遍历完了temp赋值给queue(4和2),level++为1
当queue.length(2)不为0循环:
temp为空(由于上次循环里temp放的是这一层的节点,而temp是要每次存放下一层的节点故每次for遍历此层前将temp置空)
走for遍历这一层的节点;
将 4节点放入res[level]队列 (level为1)
看看他的左右孩子是否存在,依次进入temp队列 此时temp是3节点
将 2节点放入res[level]队列 (level为1)
看看他的左右孩子是否存在,依次进入temp队列 此时temp是3和5节点
第二层遍历完了temp赋值给queue(3和5),level++为2
当queue.length(2)不为0循环:
temp为空(由于上次循环里temp放的是这一层的节点,而temp是要每次存放下一层的节点故每次for遍历此层前将temp置空)
走for遍历这一层的节点;
将 3节点放入res[level]队列 (level为2)
看看他的左右孩子是否存在(不存在),依次进入temp队列 此时temp为空
将 5节点放入res[level]队列 (level为2)
看看他的左右孩子是否存在(不存在),依次进入temp队列 此时temp依然是空
第二层遍历完了temp赋值给queue(为空),level++为3
此时queue长度为空,跳出循环,而level就是二叉树的层数(虽然从0层开始(为了和数组下标对应)但是再遍历完第二层(此时是最后一层遍历后仍然加1)为3)
然后将res数组reverse一下得到结果