2

我正在尝试编写一个函数来计算 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 那么我该如何解决这个问题？

4

2 回答 2

2

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

于 2013-03-20T19:58:00.250 回答
1

您必须累积递归调用的结果。这可以通过 来完成zero, one, two = map(sum, zip(result_right, result_left))，然后根据子项的数量添加相应的值。

请注意，我使用if/elif语句，否则当节点有两个孩子时，您的代码也会进入下一个if块中的一个孩子。

def _node_counts_aux(self, node):
    zero, one, two = 0, 0, 0
    if node is not None:
        result_right = self._node_counts_aux(node._right)
        result_left = self._node_counts_aux(node._left)
        zero, one, two = map(sum, zip(result_right, result_left))
        if not node._right and not node._left:
            zero += 1
        elif node._left and node._right:
            two += 1
        elif node._left or node._right:
            one += 1
    return zero, one, two
于 2013-03-21T21:30:39.997 回答