Если вы пытаетесь реализовать истинный поиск в ширину, вы можете упростить свое решение, используя getattr
, для обработки листьев дерева (left
или right
атрибутов, хранящих None
) и collections.deque
для более простого доступа к элементу с обоих концов.Обратите внимание, что collections.deque
содержит метод __bool__
, поэтому вам не нужно явное сравнение размеров в цикле while
.В демонстрационных целях приведенный ниже код создает полное двоичное дерево с методом __repr__
для проверки ответа, а затем предоставляет класс решения.Кроме того, чтобы найти порядок на уровне дерева, как описано в этой подобной проблеме, вы можете использовать рекурсию для более простого результата:
Реализация двоичного дерева:
import collections, random
class Tree:
full_nodes = []
def __init__(self, **kwargs):
self.__dict__ = {i:kwargs.get(i) for i in ['left', 'right', 'value']}
Tree.full_nodes.append(kwargs.get('value'))
def __bool__(self):
return bool(getattr(self, 'value'))
def __lt__(self, _node):
return self.value < getattr(_node, 'value', _node)
def insert_val(self, val):
if self.value is None:
self.value = val
else:
if val < self.value:
if self.left is None:
self.left = Tree(value = val)
else:
self.left.insert_val(val)
else:
if self.right is None:
self.right = Tree(value = val)
else:
self.right.insert_val(val)
def __repr__(self):
return f'<tree storing nodes {list(filter(None, Tree.full_nodes))}>'
@classmethod
def load_tree(cls, num=10, bounds = [1, 100]):
_t = cls()
for i in range(num):
_t.insert_val(random.choice(range(*bounds)))
return _t
Решения:
class Solution:
@staticmethod
def bfs(tree, _to_find):
queue = collections.deque([tree])
seen = []
while queue:
_current = queue.popleft()
if getattr(_current, 'value', None) == _to_find:
return True
l = list(filter(None, [getattr(_current, i, None) for i in ['left', 'right'] if getattr(_current, i, None) not in seen]))
queue.extend(l)
seen.extend(l)
return False
@staticmethod
def level_nodes(tree):
return [list(filter(None, [*(Solution.level_nodes(tree.left) if isinstance(tree.left, Tree) else [tree.left]), tree.value, *(Solution.level_nodes(tree.right) if isinstance(tree.right, Tree) else [tree.right])]))]
@classmethod
def pretty_nested(cls, t):
if t:
yield [t.value]
yield [*(list(cls.pretty_nested(getattr(t, 'left', None))) if hasattr(t, 'left') else [None]), *(list(cls.pretty_nested(getattr(t, 'right', None))) if hasattr(t, 'right') else [None])]
Действующие решения:
t = Tree.load_tree()
>>>t
<tree storing nodes [10, 82, 17, 25, 78, 93, 64, 53, 74]>
>>>Solution.bfs(t, 10), Solution.bfs(t, 200)
(True, False)
>>>list(Solution.pretty_nested(t))
[[42], [[10], [[17], [[25], []]], [82], [[78], [[64], [[53], [], [74], []]], [93], []]]]