# 层序遍历
假设我们的树节点的定义如下:
interface TreeNode<T> {
left: TreeNode | null;
right: TreeNode | null;
data: T;
}
TIP
总是按每层从左到右的顺序输出二叉树中的节点
算法实现:
/**
* 二叉树的层序遍历
* @param {TreeNode} tree 树的根节点
*/
function treeLevelTraverse(tree) {
if (!tree) {
console.log("empty tree");
return;
}
let node = tree;
let list = [];
// 将跟节点入队
list.push(node);
// 如果队列不为空,则进行遍历
while (list.length > 0) {
// 从队首取出一个元素用以处理
const curNode = list.shift();
console.log(curNode.data);
// 如果存在左子树,将左子树入队
if (curNode.left) {
list.push(curNode.left);
}
// 如果存在右子树,将右子树入队
if (curNode.right) {
list.push(curNode.right);
}
}
/**
* 因为队列先入先出的特性,所以最后的打印顺序总是按层从上至下,每层从左到右的顺序输出
*/
}
# 复杂度分析
时间复杂度O(n)
;空间复杂度O(w)
,为二叉树的最大宽度;