【算法】二叉树的层序遍历

难度：中等

题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

解题思路：

层次遍历二叉树是指按照树的层级从上至下、从左至右的顺序访问每个节点。我们可以使用广度优先搜索（BFS）策略来实现这一遍历方式。

1. 初始化：创建一个队列，并将根节点放入队列中。同时，初始化一个数组result用于存储每一层的节点值。
2. 循环处理：当队列不为空时，进行以下操作：
   ○ 获取队列的长度，这个长度代表当前层的节点数。
   ○ 遍历当前层的节点数，对于每个节点：
   ■ 将节点从队列中取出。
   ■ 将节点的值添加到result数组的当前层结果中。
   ■ 若节点有左孩子或右孩子，将它们依次加入队列中，以便下一层的遍历。
3. 返回结果：循环结束后，result数组即为层序遍历的结果。

JavaScript实现：

/**
 * 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) {
   if (!root) return []; // 如果根节点为空，直接返回空数组
   const queue = [root]; // 初始化队列，放入根节点
   const result = []; // 初始化结果数组
   while(queue.length > 0){
      const levelSize = queue.length; // 当前层的节点数
      const currentLevel = []; // 存储当前节点的值
      for(let i = 0; i < levelSize; i++){
          const currentNode = queue.shift();// 取出队首节点
          currentLevel.push(currentNode.val); // 将节点值加入当前层结果
          // 将当前节点的左右孩子加入队列（如果存在）
          if(currentNode.left) queue.push(currentNode.left);
          if(currentNode.right) queue.push(currentNode.right)
      }
      result.push(currentLevel); // 将当前层结果加入最终结果
   }
   return result;
};

这段代码首先定义了一个简单的二叉树节点类TreeNode，然后实现了levelOrder函数，该函数接收一个二叉树的根节点作为输入，返回这个二叉树的层序遍历结果。通过广度优先搜索策略，利用队列实现逐层访问，并收集每层节点的值到结果数组中。

原文地址：https://blog.csdn.net/xiaolinlife/article/details/140451533

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！