声明：本文原题主要来自力扣，记录此博客主要是为自己学习总结，不做任何商业等活动！

前面博文总结了二叉树的前序遍历、中序遍历、后序遍历，本文主要总结二叉树的层次遍历。本文通过力扣上的示例打印出二叉树每层节点。

一、二叉树层次遍历

1.1 力扣原题

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

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

1.2 题目分析

由上面题目可知，输入是一个一维数组，输出是一个二维数组。其中输入一维数组中存储的是节点元素，输出二维数组是每层节点关键字打印。故知道该题主要考察二叉树基本的层次遍历方法，需要打印出每层节点的关键字。

1.3 实现思路

二叉树的层次遍历实现思路是用一个队列记录每层节点，当记录第一层节点时，弹出第一层节点进行访问，访问的同时需要遍历对应节点的左右子节点压栈；当访问完一层节点时，此时改成节点所有左右子节点都已经压栈，由于先前循环弹出了第一层的n个节点，故当前队列只存储下一层所有节点，所以只需要将该队列大小保存，然后该轮循环中弹出这么多个节点，即可一层层访问二叉树，直到访问完截止。

1.4 具体代码实现

二叉树的层次遍历如下，打印每层节点代码如下

class Solution {
public:vector> levelOrder(TreeNode* root) {if (root == nullptr)return {};TreeNode* curNode = nullptr;vector perLevelNodes;vector> result;int count = 0;std::queue nodeQueue;nodeQueue.push(root);while (!nodeQueue.empty()) // 每轮循环，都访问一层节点{perLevelNodes.clear();count = nodeQueue.size(); // 当前层有count个节点for (int i = 0; i < count; ++i) { // 循环弹出count次节点进行访问，也就是访问该层所有节点；同时将下一层所有节点压入栈curNode = nodeQueue.front();nodeQueue.pop();perLevelNodes.push_back(curNode->val);if (curNode->left != nullptr) // 左子节点非空压入栈nodeQueue.push(curNode->left);if (curNode->right != nullptr) // 右子节点非空压入栈nodeQueue.push(curNode->right);}result.push_back(perLevelNodes); // 将每层节点数组保存起来}return std::move(result); // 返回结果数组}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！