python - 二叉搜索树中三种节点的计数(递归)

Question

我正在尝试编写一个函数来计算 Python 中二叉搜索树中三种类型的节点。它将计算并返回具有 0 个子节点、1 个子节点和 2 个子节点的节点总数。我注意到递归方法最适合这种方法而不是迭代方法。

def node_counts(self):
    """
    ---------------------------------------------------------
    Returns the number of the three types of nodes in a BST.
    Use: zero, one, two = bst.node_counts()
    -------------------------------------------------------
    Postconditions:
      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, one, two = 0, 0, 0
    if node is not None:
        if not node._right and not node._left:
            zero = 1 # I understand that the problem is here.
        if node._left and node._right:
            two = 1 + self._node_counts_aux(node._left)[2] + self._node_counts_aux(node._right)[2]
        if node._left or node._right:
            one = 1 + self._node_counts_aux(node._left)[1] + self._node_counts_aux(node._right)[1]
    return zero, one, two

"""
I am testing with this Tree:
        36
       /  \
      /    \
     6      50
    / \     / \
   4   17  49  84
       /   /   / \
      12  42  65 85

The output with this code comes to: (0, 6, 4).

"""

一栏在某种意义上是错的，但在某种意义上也是对的。那不是我关心的。我担心的是零不被计算在内。零被设置为 0 那么我该如何解决这个问题？

Answer 1

问题是方法 _node_counts_aux() 返回一个元组，但您正试图将 1 添加到它的结果中。您必须从递归调用中提取类型 0、1 和 2 的元素的计数，并改用这些值。