vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> bfs;
if (root != nullptr) bfs.push(root);
vector<vector<int>> sol;
vector<TreeNode*> temp;
vector<int> indivSol;
while (!bfs.empty()) {
int currSz = bfs.size();
for (int i = 0; i < currSz; i++) {
temp.push_back(bfs.front());
bfs.pop();
indivSol.push_back(temp.at(i)->val);
if (temp.at(i)->left != nullptr) bfs.push(temp.at(i)->left);
if (temp.at(i)->right != nullptr) bfs.push(temp.at(i)->right);
}
temp.clear();
sol.push_back(indivSol);
indivSol.clear();
}
return sol;
}
n 次(n 是树中的节点数)，但是内部 for 循环会使解决方案在 O(n^2) 时间内运行吗？由于一棵树在 2^n 层上最多有 n 节点，因此 currSz 可以随着 1 to 2 to 4 to 8 to 16 ... 的外循环的每次迭代而增长编辑:
意识到外循环只会多次运行
l，其中 l 是级别数
最佳答案
忘记一切，回想一下，当您使用此代码执行层序遍历时，您会访问每个节点一次。因此，如果树中总共有 k 节点，那么时间复杂度将为 O(k)。h : 树的高度
while 循环运行 h 次，并且在每次迭代(即在每个级别)时，它都会遍历该级别中存在的所有节点。所以类似地，这适用于每次迭代(级别)，结果为 O(n)(n 是节点总数)
关于c++ - 为什么这个层序遍历在 O(n) 时间内运行？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/63196103/