二叉树的层序遍历(按层输出),如何用队列实现?
思路:广度优先(BFS),用队列「逐层」处理,每层先记录长度再统一出队。
function levelOrder(root) {
if (!root) return []
const queue = [root], res = []
while (queue.length) {
const size = queue.length // 当前层节点数
const level = []
for (let i = 0; i < size; i++) {
const n = queue.shift()
level.push(n.val)
if (n.left) queue.push(n.left)
if (n.right) queue.push(n.right)
}
res.push(level)
}
return res
}- 时间
O(n),空间O(n)(队列最坏存满一层) - 变体:之字形层序(偶数层反转)、求树的最大深度