Блог

Главная - Вопросы по программированию - Почему «пока len (x)» дает правильный ответ, а «пока x» дает превышенный лимит времени?

Почему «пока len (x)» дает правильный ответ, а «пока x» дает превышенный лимит времени?

#python #algorithm #data-structures #tree

#python #алгоритм #структуры данных #дерево

Вопрос:

Учитывая двоичное дерево, соедините узлы, которые находятся на одном уровне. Вам будет предоставлен дополнительный указатель nextRight для того же.

Изначально все указатели nextRight указывают на значения мусора. Ваша функция должна установить эти указатели так, чтобы они указывали рядом справа для каждого узла.

        10                          10 ------> NULL
      /                        /      
     3   5       =>            3 ------> 5 --------> NULL
    /                      /           
   4   1   2                4 --> 1 -----> 2 -------> NULL

Мой код:

 def connect(root):
    q = []
    q.append(root)
    while q:
        x = len(q)
        for i in range(x):
            curr_node = q[0]
            if i!=x-1:
                curr_node.nextRight = q[1]
            if curr_node.left:
                q.append(curr_node.left)
            if curr_node.right:
                q.append(curr_node.right)
            q.pop(0)
    '''
    :param root: root of the given tree
    :return: none, just connect accordingly.
    {
        # Node Class:
        class Node:
            def __init__(self,val):
                self.data = val
                self.left = None
                self.right = None
                self.nextRight = None
    }

Обратите внимание, что когда я использую while q , я получаю превышение срока, а когда я использую while len(q) , я получаю правильный ответ. Кто-нибудь может сказать мне причину, почему это так?

Комментарии:

1. Ваш код отлично работает для меня с обоими while q: и while len(q): . Вы забываете указать nextRight None , когда i == x-1 . В нем говорится, что nextRight это инициализируется мусором.

2. Если вы хотите немного оптимизировать этот код, используйте коллекции. скорее, чем список. удаление первого элемента списка происходит медленно, но удаление из очереди оптимизировано для добавления и удаления с обоих концов.

3. while q и while len(q) не должно иметь какой-либо заметной разницы во времени выполнения.

4. Возможно, приведите какой-нибудь пример ввода с бенчмаркингом, чтобы показать разницу во времени? «На каком-то (неуказанном) веб-сайте истекает время ожидания, когда я вношу это изменение» недостаточно информации, чтобы определить, связана ли ошибка с вашим кодом или с веб-сайтом.