102. 二叉树的层序遍历
102. 二叉树的层序遍历
力扣题目链接[1]
给你二叉树的根节点 root ，返回其节点值的 「层序遍历」 。（即逐层地，从左到右访问所有节点）。
示例1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
「提示：」
- 树中节点数目在范围
[0, 2000]内 1000 <= Node.val <= 1000
思路：
二叉树的层序遍历，也就是广度优先遍历。需要借用队列来实现。队列的特点是：先进先出。在JS中，并没有提供原生的队列供我们使用，因此我们需要使用现有的数据结构来实现列表。可以使用数组或者链表的方式实现队列，这里选择使用数组实现。从尾部添加(push)元素，从头部弹出(shift)元素。
具体代码如下：
BFS
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
let result = [];
if (!root) return result; // 如果二叉树为空，则返回空数组
let queue = [root]; // 初始化队列
while(queue.length) {
let temp = [];
let cur = [];
while(queue.length) { // 遍历每一层节点
const node = queue.shift();
cur.push(node.val);
if (node.left) temp.push(node.left);
if (node.right) temp.push(node.right);
}
result.push(cur); // 每一层节点值组成的数组
queue = temp; // 将下一层节点信息赋值给队列
}
return result;
};
总结
本题的难点在于如何将每层的节点放入一个数组中。当每一层节点刚好遍历完时，队列中所存在的节点刚好就是下一层的所有节点。我们便可以利用这个信息，来通过内层循环处理每一层的节点。
做法就是不断的弹出队头节点，并将节点的值放入cur数组中。如果当前节点有左右子节点，则继续放入队尾，充当下一层的节点。当遍历完当前层节点时，将cur数组放入结果数组当中。同时需要注意，要将内层循环的子节点放入临时数组中，循环结束后再赋值给队列。如果不如此做，内层循环就永远不为空，直到遍历完所有的二叉树节点。最后的结果就是一维数组了。
参考资料
[1]
力扣题目链接: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-04-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
