<h2>解决方案</h2>
<p>考虑到您想要双向搜索(即能够同时搜索下属和经理),您将需要某种类型的树结构,对节点之间的双向链接进行编码。下面是一个实现这样一个树的类:</p>
<pre><code>class Node:
def __init__(self, val):
"""initialize a node with the worker id value
"""
self._children = []
self._parent = None
self.val = val
def link(self, *node):
"""create a parent-child link between this (parent) node and one
or more (children) nodes
"""
for n in node:
n._parent = self
self._children.append(n)
def get(self):
"""depth-first recursive get
"""
return [x for y in ([n.val] + n.get() for n in self._children) for x in y]
def getparents(self):
"""walks up parents (currently there's at most one parent per-node)
"""
return [] if self._parent is None else [self._parent.val] + self._parent.getparents()
class Tree:
def __init__(self, idlists):
"""initialize the tree as per the OP's example input
"""
self._nodes = {}
for topid,idlist in enumerate(idlists):
self.add(topid, idlist)
def __getitem__(self, key):
return self._nodes[key]
def _getnode(self, i):
"""get or create the node with id=i.
Avoid constructing new Nodes if we don't have to
"""
if i in self._nodes:
return self._nodes[i]
else:
n = self._nodes[i] = Node(i)
return n
def add(self, topid, idlist):
"""create a node with id=topid (if needed), then add
child nodes, one per entry in idlist
"""
self._getnode(topid).link(*(self._getnode(i) for i in idlist))
</code></pre>
<h2>测试一下</h2>
<p>下面是如何使用上面定义的<code>Tree</code>类来解决指定的问题:</p>
^{pr2}$
<h2>漫谈</h2>
<p>这是一个经典的CS-chestnut,在现代编码教程中似乎没有太多的曝光(我认为,因为以前用树来解决的许多问题现在有了更简单的哈希表/基于dict的答案)。在</p>