日野弥生：勉強しよう
LeetCode 102 - 二叉树的层序遍历
发表于2025年02月16日
层次遍历属于广度优先搜索，优先使用队列数据结构即可处理。本题要求不同层次的数据放在不同的向量中，最后存储于二维向量。需要在遍历过程动态resize向量的大小。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(!root)
return {};
/* 通过键值对方式存储层数 */
queue<pair<TreeNode*, int>> q;
vector<vector<int>> result{};
q.push(make_pair(root, 0));
while(!q.empty())
{
auto curr = q.front();
q.pop();
/* 判断是否需要扩容 */
if(curr.second >= (int)result.size())
{
result.resize(curr.second + 1);
}
result[curr.second].push_back(curr.first->val);
/* 层次遍历左子和右子 */
if(curr.first->left)
q.push({curr.first->left, curr.second + 1});
if(curr.first->right)
q.push({curr.first->right, curr.second + 1});
}
return result;
}
};