同树| leetcode错误解决方案的复杂性分析

Question

关于leetcode问题解决方案的空间复杂性分析，我有一个问题：100。同一棵树

问题是： 给定两个二叉树，编写一个函数来检查它们是否相同。如果两个二叉树在结构上相同，并且节点具有相同的值，则认为它们是相同的。你知道吗

解决方案代码：

from collections import deque
class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """    
        def check(p, q):
            # if both are None
            if not p and not q:
                return True
            # one of p and q is None
            if not q or not p:
                return False
            if p.val != q.val:
                return False
            return True

        deq = deque([(p, q),])
        while deq:
            p, q = deq.popleft()
            if not check(p, q):
                return False

            if p:
                deq.append((p.left, q.left))
                deq.append((p.right, q.right))

        return True

我的问题是：

Leetcode中解的空间复杂度分析表明，对于完全不平衡树，保持一个deque是O（N）。然而，我认为空间复杂度绝对不是O（N）。我用下面的例子来说明原因：假设root=1，根。左= 2, 根。左。左= 3, 根。左。左.left=4，N为无。下面是德克的不同阶段。对于每个阶段，我们只保留一个项目，然后添加两个项目，除非遇到N

[1]->；[2，N]->；[N，3，N]->；[3，N]->；[N，4，N]->；[4，N]->；[N，N，N]

从上面的deque可以看出，大小永远不会达到N（其中N是节点数）

我可以看出这个算法的空间复杂度不是O（N）（我说的对吗？），但我不能确定是什么。你知道吗