Question

因此,正如你从功能定义中可以看到的那样,这一功能应当确定 Bin树的类型,但我并没有发现错误,尽管我认为我的产出是正确的,但我有辅助方法通过生物浓缩系数进行重新搜索,并检查我们是否为零、一、二。如果我对《巴塞尔协议书》提出以下意见:

    22
   /  
  12   30
 /    / 
8  20 25 40

它的回报为0,0,1 ,但我不认为是正确的,它是否应该返回4,3 ? 自22、12和30起,有两条孩子,有8,20,25个孩子,有40个孩子是零。任何帮助都将受到高度赞赏。

Here is my code:

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,1人。

Answer 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)

更清洁得多;必须环绕的数据较少。为节点假设真相价值是安全的。

还指出, trav令无关紧要。

友情链接