returns 一个 2D ArrayList 的 BFS 算法的时间复杂度是多少？

Question

我想弄清楚这种方法的时间复杂度是多少，以便更好地计算时间复杂度。其他人告诉我，这将是最坏的情况 O(n^2) （n 是树中的元素）但我很困惑，因为外部 while 循环只会达到级别的数量，而不是总元素。

任何帮助都会很棒！

public List returnLevelOrder(TreeNode root) { ret = new ArrayList ();

Queue<Integer> queue = new List<Integer>();

if(root==null){
    return ret;
}

queue.add(root);

while(!queue.empty()) {

    ArrayList<Integer> level = new ArrayList<Integer>();

    int levelSize = queue.size();

    while(levelSize >0) {
        TreeNode currNode = queue.poll();
        level.add(currNode.val);
        levelSize--;

        if(currNode.left != null) {
            queue.add(currNode.left.val);
        }

        if(currNode.right != null) {
            queue.add(currNode.right.val);
        }

    }
    ret.add(level);

}

return ret;

}

Answer 1

它是 O(n) - 你访问所有元素一次 - 它是一个迭代树遍历。