借用一个辅助数据结构即队列来实现,队列先进先出,符合一层一层遍历的逻辑,而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历,只不过我们应用在二叉树上
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
#include <vector>
#include <queue>using namespace std;class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result; // 存储最终结果if (root == nullptr) {return result; // 空树直接返回}queue<TreeNode*> q; // 创建队列用于BFSq.push(root); // 根节点入队while (!q.empty()) {int levelSize = q.size(); // 当前层的节点数vector<int> currentLevel; // 存储当前层的节点值// 处理当前层的所有节点for (int i = 0; i < levelSize; ++i) {TreeNode* currentNode = q.front(); // 取出队首节点q.pop(); // 出队currentLevel.push_back(currentNode->val); // 存储节点值// 将左右子节点入队(如果存在)if (currentNode->left != nullptr) {q.push(currentNode->left);}if (currentNode->right != nullptr) {q.push(currentNode->right);}}result.push_back(currentLevel); // 将当前层加入结果}return result;}
};