在一次在线评估中，我被要求计算一棵树上的叶子数量。该树以父数组表示形式给出，这意味着该树有n个带有标签0、1、2，..，n-1的节点，并且传递了长度为n的数组p，其中p [i]返回的标签为节点i的父节点，除非当i是树的根时（在这种情况下p [i]为-1）。
我想要注意的一件事是问题如上所述，因此没有额外的条件，例如它是一棵二叉树。
我认为这是一个相当简单的问题，但是我提交的代码在测试平台上无法通过“小树案例”（无法看到测试案例）。它通过了其他测试，包括对一棵大树的性能测试。我已经考虑了一段时间，但是我仍然看不到我的算法或处理某些边缘情况的缺陷是什么。我想要注意的一件事是问题如上所述，因此没有额外的条件，例如它是一棵二叉树。
def countLeaves(p):
n = len(p)
if p is None or n == 0 : return 0
if n == 1 or n == 2 : return 1
leaves = set(range(n))
for i in range(n):
if p[i] == -1: # i is root of tree with >1 node, can't be a leaf
leaves.discard(i)
else: # p[i] is parent of node i, can't be a leaf
leaves.discard(p[i])
return len(leaves)
在尝试修复失败的“小树情况”时，我还尝试了如果p为None则返回None，如果n == 0则返回None，或者两个修改一起进行，但均未成功。如果有人能指出我的代码中可能是什么错误，我将不胜感激。谢谢。
最佳答案
我会尝试这样的：
def countLeaves(p):
n = len(p)
if p is None or n < 2 : return 0
leaves = set(range(n))
for i in range(n):
if p[i] == -1: # i is root of tree with >1 node, can't be a leaf
leaves.discard(i)
else: # p[i] is parent of node i, can't be a leaf
leaves.discard(p[i])
return len(leaves)
唯一真正的变化是，它认为具有单个节点的树没有叶子。
根据Wolfram Mathworld：
无根树的叶子是顶点度为1的节点。请注意，对于有根或种植的树，根顶点通常不被视为叶节点，而其他所有度数为1的节点。