python - 查找是否所有叶节点都处于相同高度

Question

我在 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] 但我也想知道它们是否在同一层。

首先想到的是求起始节点到叶节点的路径，然后求其长度。但是我们能做得更好吗？甚至在上面提到的相同函数中，我们返回叶子及其高度。

Answer 1

您可以使用 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]]