二叉搜索树节点计数方法输出错误排查求助

你的代码问题出在递归调用子树时没有接收并累加子树的计数结果，每次递归只统计了当前节点的类型，完全忽略了左右子树里的节点计数，所以最终只返回了根节点的统计值。

修复后的代码 #

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

def node_counts_aux(self, node):
    zero = 0
    one = 0
    two = 0

    if node is None:
        return zero, one, two

    # 接收左右子树的计数结果
    zero_left, one_left, two_left = self.node_counts_aux(node._left)
    zero_right, one_right, two_right = self.node_counts_aux(node._right)

    # 累加子树的计数到当前统计值
    zero += zero_left + zero_right
    one += one_left + one_right
    two += two_left + two_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

关键改动说明 #

1. 接收子树返回值：递归调用左右子树时，将它们返回的三类节点计数分别保存，不再丢弃结果。
2. 累加子树计数：把左右子树的计数先加到当前的zero、one、two变量中。
3. 统计当前节点：最后判断当前节点的子节点情况，给对应的计数器加1。

修复后，针对你给出的BST结构，会正确返回预期的(4, 0, 3)：8、20、25、40被统计为零子节点，22、12、30被统计为双子节点，没有单子节点。

内容的提问来源于stack exchange，提问作者michelle