为什么这个层序遍历在 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节点总数）