题目描述
实现思路
二叉树的层次遍历,是与广度优先搜索的特点相对应的
原来的广度优先搜索代码如下:
var bfs=function(root){
var visited=new Array()
if(root!==null){
var queue=new Array
queue.push(root)
while(queue.length > 0){
let temp=queue.shift()
visited.push(temp)
if(temp.left){
queue.push(temp.left)
}
if(temp.right){
queue.push(temp.right)
}
}
}
return visited
}
在这个基础上,我们需要使得:
在每一轮循环开始之前,queue中的节点都是处于同一层级的
这就需要我们在上一次循环中,将queue中所有节点的子节点都放入queue中
也就是说,需要写一个嵌套的循环
利用内层循环来遍历queue:
先拿出队首元素(出队)
再将其子节点放入queue
内层循环结束后,将这一轮出队的元素,推入最终的结果数组中
代码实现(Javascript)
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
var visited=new Array()
if(root!==null){
var queue=new Array()
queue.push(root)
while(queue.length > 0){
let levelSize=queue.length
let currentLevel=new Array()
for(let i=0;i<levelSize;i++){
let temp=queue.shift()
currentLevel.push(temp.val)
if(temp.left){
queue.push(temp.left)
}
if(temp.right){
queue.push(temp.right)
}
}
visited.push(currentLevel)
}
}
return visited
};