c++ - 为什么这个层序遍历在 O(n) 时间内运行？

Question

    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;
    }

我知道外部 while 循环将运行 n 次( n 是树中的节点数)，但是内部 for 循环会使解决方案在 O(n^2) 时间内运行吗？由于一棵树在 2^n 层上最多有 n 节点，因此 currSz 可以随着 1 to 2 to 4 to 8 to 16 ... 的外循环的每次迭代而增长
编辑:
意识到外循环只会多次运行 l，其中 l 是级别数

Answer 1

忘记一切，回想一下，当您使用此代码执行层序遍历时，您会访问每个节点一次。因此，如果树中总共有 k 节点，那么时间复杂度将为 O(k)。h : 树的高度
while 循环运行 h 次，并且在每次迭代(即在每个级别)时，它都会遍历该级别中存在的所有节点。所以类似地，这适用于每次迭代(级别)，结果为 O(n)(n 是节点总数)