В Python преобразуйте список целых чисел в двоичное дерево

У меня есть список целых чисел, которые я хочу преобразовать в двоичное дерево в Python. Каждый элемент должен перейти на следующую доступную позицию в дереве слева направо.

Например, список целых чисел может быть

root = [3,9,20,None,None,15,7]

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

root = [2,None,3,None,4,None,5,None,6]

каждый элемент идет на своем уровне. (Это массивное представление двоичных деревьев взято из Leetcode, например (https://leetcode.com/problems/minimum-depth-of-binary-tree/).)

Я могу решить проблему, когда список является исчерпывающим, т.е. каждая позиция в дереве указана, даже если ее родитель(и) - None; см. ниже.

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def array_to_binary_tree(array):
    n = len(array)
    node = Node(array[0])
    nodes = []
    nodes.append(node)
    for i in range(0, n):
        left_index = i * 2 + 1
        if left_index < n:
            node_left = Node(array[left_index])
            nodes.append(node_left)
            nodes[i].left = node_left
        right_index = i * 2 + 2
        if right_index < n:
            node_right = Node(array[right_index])
            nodes.append(node_right)
            nodes[i].right = node_right
    root = nodes[0]
    return root

Но я не могу решить это, когда массив дает минималистское представление.

В root = [2,null,3,null,4,null,5,null,6]null означает None я полагаю!?

destructioneer 10.07.2023 12:16

@destructioneer Да, null означает «Нет», спасибо. Теперь это исправлено.

Soulfire 10.07.2023 12:19

Как именно [2,None,3,None,4,None,5,None,6] представляет собой дерево. Можете ли вы показать желаемый результат?

user2390182 10.07.2023 12:34

Это явно проблема LeetCode, потому что они используют null в текстовом представлении дерева/узла, которое вы скопировали и вставили. Есть ли конкретная проблема LeetCode, которую вы пытаетесь решить?

Abhijit Sarkar 10.07.2023 12:54

Этот синтаксис представления двоичного дерева массивом и примеры массивов, которые я показал, исходят от Leetcode. Я отредактировал, чтобы включить это в свой вопрос.

Soulfire 10.07.2023 14:39
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
0
5
55
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Ваш код, кажется, предполагает, что входное дерево является полным двоичным деревом, поскольку вы используете формулу i * 2 + 1. Но дерево, представленное в примере, не является полным, и эта формула работать не будет.

Вот функция, которую вы могли бы использовать:

from collections import deque

def array_to_binary_tree(lst):
    if not lst:
        return
    values = iter(lst)
    root = Node(next(values))
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node:
            # Get next two values from input list, and 
            #   if they are not None, create a node for them
            children = [
                None if value is None else Node(value)
                for value in (next(values, None), next(values, None))
            ]
            # Append these two to the queue, and also attach them in the tree
            queue.extend(children)
            node.left, node.right = children

    return root

Вот альтернатива, которая не вызывает iter явно, но использует for для итерации значений из входного списка:

def array_to_binary_tree(lst):
    if not lst:
        return
    node = root = Node(lst[0])
    queue = deque()
    for i, value in enumerate(lst[1:]):
        if value is not None:  # A node to create?
            queue.append(Node(value))
            if i % 2:  # At odd iterations we attach it as a right child
                node.right = queue[-1]
            else:  # At even iterations we attach it as a left child
                node.left = queue[-1]
        if i % 2 and queue:  # After odd iterations we grab a next parent
            node = queue.popleft()

    return root

Моя единственная претензия к этому — использование списка в качестве очереди =)

user2390182 10.07.2023 12:37

@user2390182 user2390182, хорошо, вместо этого использовал двухуровневую очередь.

trincot 10.07.2023 12:40

Спасибо! Не могли бы вы, если хотите, объяснить, что делает этот код, и, в частности, почему нам нужно использовать iter()?

Soulfire 10.07.2023 12:57

Нет абсолютной необходимости использовать iter, это просто приятная особенность Python. Вы также можете использовать индексную переменную i, как и вы, и увеличивать ее каждый раз, когда вы берете значение из списка ввода.

trincot 10.07.2023 12:58

Я добавил несколько комментариев к коду и альтернативу, которая не использует iter.

trincot 10.07.2023 13:18

Другие вопросы по теме