时间戳

首页 > 解决方案 > 代码不起作用树 BFS 搜索

python - 代码不起作用树 BFS 搜索

问题描述

我编写了一个树级顺序遍历，虽然我的代码有正确的输出，但它会抛出一个

第 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

标签： pythontreebreadth-first-search

解决方案

如果您尝试实现真正的广度优先搜索，您可以使用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], []]]]

推荐阅读