Код не работает Дерево поиска BFS - PullRequest
Новая
       15

Код не работает Дерево поиска BFS

0 голосов
/ 31 мая 2018

Я закодировал обход порядка на уровне дерева и, хотя мой код имеет правильный вывод, он выдает

Строка 21: AttributeError: объект 'NoneType' не имеет атрибута 'val'

Я знаю, что одно из значений где-то возвращает Null, и я не могу найти где. 

# Definition for a binary tree node. 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

import queue
class Solution(object):
    def levelOrder(self, root):
        L = queue.Queue()
        local = []
        result = []
        L.put(root)
        counter = 0
        while not L.empty():
            counter = L.qsize()
            local = []
            while counter >0:
                node = L.get()
                local.append(node.val)
                if(node.left):
                    L.put(node.left)
                if(node.right):
                    L.put(node.right)
                counter -=1
            result.append(local)   
        return result

1 Ответ

0 голосов
/ 31 мая 2018

Если вы пытаетесь реализовать истинный поиск в ширину, вы можете упростить свое решение, используя 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], []]]]
...