二叉树的层序遍历 js
时间: 2023-09-30 07:06:24 浏览: 44
二叉树的层序遍历可以使用广度优先搜索(BFS)算法来实现。具体实现步骤如下:
1. 定义一个队列,初始时将根节点入队。
2. 当队列非空时,依次取出队列中的节点,将其值存入结果数组中,并将其左右子节点入队。
3. 重复步骤2,直到队列为空。
下面是 JavaScript 代码实现:
```javascript
function levelOrder(root) {
if (!root) return []
const res = []
const queue = []
queue.push(root)
while (queue.length) {
const level = []
const size = queue.length
for (let i = 0; i < size; i++) {
const node = queue.shift()
level.push(node.val)
if (node.left) queue.push(node.left)
if (node.right) queue.push(node.right)
}
res.push(level)
}
return res
}
```
其中,`root` 表示二叉树的根节点,`res` 用于存储结果,`queue` 为队列,初始时将根节点入队。在循环中,每次取出队列中的节点,将其子节点入队,并将节点的值存入当前层的结果数组 `level` 中。当当前层的节点全部处理完后,将 `level` 数组存入 `res` 数组中,继续处理下一层。最终返回结果数组 `res`。