查找所有叶节点是否处于同一高度

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变量。当你找到一片叶子时，把叶子的编号和深度加在一个容器里

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]]