时间戳

首页 > 解决方案 > 为什么这个级别顺序遍历在 O(n) 时间内运行？

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

问题描述

    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在 level 上最多有节点n，currSz因此外循环的每次迭代都可以从1 to 2 to 4 to 8 to 16 ...

编辑：意识到外循环只会运行l很多次，其中l级别数是多少

标签： c++algorithmbig-o

解决方案

忘记一切，回想一下，当您使用此代码执行级别顺序遍历时，您会访问每个节点一次。因此，如果树中总共有k节点，那么时间复杂度将为 O(k)。

h : 树的高度

while 循环运行h多次，并且在每次迭代（即在每个级别）时，它都会遍历该级别中存在的所有节点。所以类似地，这适用于导致 O(n) 的每次迭代（级别）（n节点总数）

推荐阅读