Блог

Я работал над проблемой Инвертирования двоичного дерева итеративным способом.

код:

 def swap(node):

    if node is None:
        return None

    temp = node.left
    node.left = node.right
    node.right = node.left


def levelOrder(root):
    if node is None:
        return None

    q = deque()
    node = root
    q.append(node)

    while q:
        currNode = q.popleft()

        if currNode.left:
            q.append(currNode.left)
        if currNode.right:
            q.append(currNode.right)

        swap(currNode)

    return root
 

Я не в состоянии понять или рассчитать сложность пространства в лучшем и худшем случаях. Временная сложность Я могу понять ее O(N), потому что нам придется посетить каждый узел, но мне нужна помощь в понимании сложности пространства(я немного погуглил, и там также указано, что ее O(N) для пространства). Мы очень ценим любую помощь.

Если вы заметите, что в вашей очереди никогда не будет всех N узлов одновременно. Однако, чтобы проверить сложность пространства наихудшего случая, максимальное количество узлов, которое оно может иметь, будет составлять все конечные узлы. В идеально сбалансированном двоичном дереве максимальное количество конечных узлов будет (N/2). Следовательно, сложность пространства равна O(N/2), что равно O(N).

Программе требуется O(n) дополнительного места для хранения узлов на любом уровне двоичного файла. Наихудший случай происходит, когда у нас есть полное двоичное дерево. В этом случае последний уровень имеет n/2 числа узлов. Таким образом, общая пространственная сложность будет O(n) для хранения узлов, которые не будут выходить за пределы n, а временная сложность будет O(n), поскольку вы посещаете все узлы в дереве.