python - 使用 BFS 在二叉树中查找并排序表兄弟

Question

我正在尝试识别二叉树中特定家庭成员的所有表 sibling 的姓名。 输入数据是以下格式的列表的列表:

family = 
[
['George', 75, ['Bob', 'Vicky']],
['Bob', 48, ['Tom', 'Sophie']],
['Vicky', 42, ['Karen']], 
['Tom', 23, []], 
['Sophie', 21, []], 
['Karen', 19, []]
]

其中每个列表代表[人，年龄，[child1，child2]] 每人最多可生育 2 个 child 。 parent 的信息总是先于 child 的信息给出，并且没有两个名字是相同的。表兄弟应该首先输出最小的。如果表 sibling 年龄相同，则应按字母顺序排列。

示例函数和输出:

>>>表兄弟(人，家庭)

>>> ['表弟1'，'表弟2'，...]

到目前为止我的尝试:

import math
import operator

def BFS(tree,level=["brown"]):
    """breadth-first search on tree."""
    bfs_list = []
    if len(level) > 0:
        bfs_list += level
        sub_level = []
        for vertex in level:
            if vertex not in tree:
                continue
            sub_level += tree[vertex]
        bfs_list += BFS(tree,sub_level)
    return bfs_list

def siblings(g,h,lst):
    """determine if two nodes are sibling."""
    return any([(g in lst[k]) and (h in lst[k]) for k in lst])

def parent_child(a,b,lst):
    """determine if two nodes have a parent-child relationship."""
    return any([(a in lst[b]), (b in lst[a])])

def cousins(p, people):
    """determine cousins of a family member."""
    famdict = {lst[0]:lst[2] for lst in people}
    agelst = sorted([(j[0], j[1]) for j in people], key=operator.itemgetter(1, 0))
    names = BFS(famdict, [people[0][0]])
    i = names.index(p)+1
    s = math.floor(math.log2(i))
    e = 1 + s
    pcuz = names[2**s-1:(2**e)-1]
    f = [n for n in pcuz if all([(not parent_child(p,n,famdict)), (not siblings(p,n,famdict))])]
    return [q[0] for q in agelst if q[0] in f]

示例输入和输出:

>>> cousins("Tom", family)

>>> ['Karen']

到目前为止，我的实现似乎有效，但有时由于运行时错误而超时。我该如何解决这个问题？

Answer 1

一种可能是找到家庭成员到目标成员的路径，然后对返回的结果进行备份:

family = [['George', 75, ['Bob', 'Vicky']], ['Bob', 48, ['Tom', 'Sophie']], ['Vicky', 42, ['Karen']], ['Tom', 23, []], ['Sophie', 21, []], ['Karen', 19, []]]
def paths(d, s, t, c = []):
   if s == t:
      yield c
   else:
      for i in d[s]['children']:
        yield from paths(d, i, t, c+[s])

def cousins(person, family):
  f = {a:{'age':b, 'children':c} for a, b, c in family}
  r = max([i for a in f for i in paths(f, a, person)], key=len)
  if len(r) < 2:
     return []
  *_, g, p = r
  return sorted([i for b in f[g]['children'] for i in f[b]['children'] if b != p], key=lambda x:(f[x]['age'], x))


print(cousins('Tom', family))
print(cousins('Bob', family))

输出:

['Karen']
[]