所以基本上，正如您从函数定义中看到的那样，该函数应该确定二叉搜索树的节点类型，我没有收到错误，但是我认为我的输出不正确，我有一个辅助方法递归地搜索 BST 并检查它是零、一还是二。如果我在下面输入这个 BST：
22
/ \
12 30
/ \ / \
8 20 25 40
它返回 0,0,1 但我认为这是不正确的，它不应该返回 4,0,3 吗？因为 22,12 和 30 是二，因为它们有两个子节点，而 8,20,25 和 40 是零，因为它们指向叶子节点。任何帮助将不胜感激！
这是我的代码：
def node_counts(self):
"""
---------------------------------------------------------
Returns the number of the three types of nodes in a BST.
Use: zero, one, two = bst.node_counts()
-------------------------------------------------------
Returns:
zero - number of nodes with zero children (int)
one - number of nodes with one child (int)
two - number of nodes with two children (int)
----------------------------------------------------------
"""
zero, one, two = self.node_counts_aux(self._root)
return zero, one, two
return
def node_counts_aux(self, node):
zero = 0
one = 0
two = 0
if node is None:
return zero, one, two
else:
self.node_counts_aux(node._left)
print(node._value)
self.node_counts_aux(node._right)
if node._left is not None and node._right is not None:
two += 1
elif (node._left is not None and node._right is None) or (node._left is None and node._right is not None):
one += 1
else:
zero += 1
return zero, one, two
我目前正在进行中序遍历，我期待的是这个 4,0,3 而不是这个 0,0,1
递归的一个常见错误是忘记使用返回值。您需要将它们传递到调用树中，以便它们在顶层“计数”：
def node_counts_aux(self, node):
zero = 0
one = 0
two = 0
if node is None:
return zero, one, two
z, o, t = self.node_counts_aux(node._left)
zero += z
one += o
two += t
z, o, t = self.node_counts_aux(node._right)
zero += z
one += o
two += t
if node._left and node._right:
two += 1
elif node._left or node._right:
one += 1
else:
zero += 1
return zero, one, two
也就是说，通常我更喜欢内部函数而不是辅助函数，并使用列表而不是不同的变量：
def node_counts(self):
counts = [0, 0, 0]
def traverse(self, node):
if not node:
return
traverse(node._left)
traverse(node._right)
if node._left and node._right:
counts[2] += 1
elif node._left or node._right:
counts[1] += 1
else:
counts[0] += 1
traverse(self._root)
return tuple(counts)
干净多了。