У меня есть список целых чисел, которые я хочу преобразовать в двоичное дерево в 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
Но я не могу решить это, когда массив дает минималистское представление.
@destructioneer Да, null означает «Нет», спасибо. Теперь это исправлено.
Как именно [2,None,3,None,4,None,5,None,6]
представляет собой дерево. Можете ли вы показать желаемый результат?
Это явно проблема LeetCode, потому что они используют null
в текстовом представлении дерева/узла, которое вы скопировали и вставили. Есть ли конкретная проблема LeetCode, которую вы пытаетесь решить?
Этот синтаксис представления двоичного дерева массивом и примеры массивов, которые я показал, исходят от Leetcode. Я отредактировал, чтобы включить это в свой вопрос.
Ваш код, кажется, предполагает, что входное дерево является полным двоичным деревом, поскольку вы используете формулу 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 user2390182, хорошо, вместо этого использовал двухуровневую очередь.
Спасибо! Не могли бы вы, если хотите, объяснить, что делает этот код, и, в частности, почему нам нужно использовать iter()?
Нет абсолютной необходимости использовать iter, это просто приятная особенность Python. Вы также можете использовать индексную переменную i
, как и вы, и увеличивать ее каждый раз, когда вы берете значение из списка ввода.
Я добавил несколько комментариев к коду и альтернативу, которая не использует iter
.
В
root = [2,null,3,null,4,null,5,null,6]
null
означаетNone
я полагаю!?