此代码的时间复杂度是多少？
if not root:
return 0
if root.left is None and root.right is None:
return 1
que = []
que.append(root)
maximum = 0
while que:
for i in range(len(que)):
node = que.pop(0)
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
maximum += 1
return maximum
您基本上正在访问二进制树的所有节点。
因此，时间&空间复杂度为O(N((N==#个节点(。
编辑：由于您已将列表用于队列，时间复杂度为O(N^2(，但还有一扇改进之门，可以将性能提高到O。
详细信息：
时间复杂性：您使用的是列表，而不是内置队列或deque列表的append()或pop()成本O(1(，但pop(0)成本O(N(。因此，您的代码并不高效。仅仅因为您选择用作队列的数据结构，就需要O(N^2(。使用内置的CCD_ 4或CCD_；弹出第一个元素。如果是，则时间复杂度将为O(N(。
空间复杂性：该算法一次遍历二叉树一个级别，因此在包含叶节点的最高级别达到队列中项目的最大数量
完整的二叉树有(n+1(/2个叶节点O((n+1(/2(=O(n(。
我也同意时间&空间复杂度为O(n)，其中n是代码的数量。然而，我认为对结果的更详细解释如下(假设root是树的根(：
- 时间复杂度：每个节点只进入
que一次，离开que一次。节点离开时，最多执行2次检查和2次追加。当que为空时，程序结束，导致(2+2)*n=4n --> O(n)的时间复杂度 - 空间复杂度：
que在任何时候都不能容纳图中的所有节点，因此空间复杂度为O(n)