我在 Python 中有一个字典形式的邻接表:
{1:[2,3], 2:[4,5,6], 3:[7,8]}
我的 findleaf() 看起来像这样
def findleaf(d):
keylist= list(d.keys())
leaf = []
for i in d:
valList = d[i]
for j in valList:
if j not in keylist:
leaf.append(j)
return leaf
所以上述方法返回的叶子为 [4,5,6,7,8] 但我也想知道它们是否在同一层。
首先想到的是求起始节点到叶节点的路径，然后求其长度。 但是我们能做得更好吗？甚至在上面提到的相同函数中，我们返回叶子及其高度。
最佳答案
您可以使用 DFS 并维护一个 DEEP 变量。当您找到一片叶子时，将叶子的编号和 DEEP 添加到容器中。
d = {1:[2,3],2:[4,5,6], 3:[7,8]}
ans = []
deep = 1
keylist = list(d.keys())
def findleaf(n,deep):
if n not in keylist:
ans.append([n,deep])
else:
l = d[n]
for i in l:
findleaf(i,deep+1)
findleaf(1,deep)
print(ans)
输出: [[4, 3], [5, 3], [6, 3], [7, 3], [8, 3]]
关于python - 查找是否所有叶节点都处于相同高度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54061531/