广度优先遍历 BFS
解题思路
该方法比较重要，对二叉树的很多其他的操作，例如：
- 统计二叉树中叶子节点个数；
- 获取二叉树的宽度；
- 判断两颗二叉树是否相等；
- 求二叉树的深度等，都是基于层次遍历而实现的；
遍历方式：
- 要进行层次遍历，需要借助一个队列；
- 首先将二叉树的根节点入队列，然后出队，访问该节点，如果它的左子树不空，则将左子树的根节点入队；
- 如果它的右子树不为空，则将右子树的根节点入队；
- 然后出队，对出队节点进行访问，如此反复，直到队列为空；
图解
复杂度
-
时间复杂度：
O(n)，每个点进队出队各一次； -
空间复杂度：
O(n)，队列中元素的个数不超过 n 个；
代码实现
var levelOrder = function (root) {
if (root === null) return [];
const res = [];
const queue = [root]; // 声明队列用于存储后续数据
// 遍历队列
while (queue.length) {
let curLevel = []; // 针对本轮操作，创建一个数组
let len = queue.length; // 一层的数据量
while (len--) {
// 将本次操作的结点出队
const node = queue.shift();
curLevel.push(node.val);
// 检测是否存在左右子结点，如果有，入队即可
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
res.push(curLevel);
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 145. 二叉树的后序遍历
上一篇
评论
