力扣题目链接[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)元素。
具体代码如下:
/**
* 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/