python - 如何修复计数功能

Question

class TN:
    def __init__(self,value,left=None,right=None):
        self.value = value
        self.left  = left
        self.right = right

def list_to_tree(alist):
    if alist == None:
        return None
    else:
        return TN(alist[0],list_to_tree(alist[1]),list_to_tree(alist[2])) 

def str_tree(atree,indent_char ='.',indent_delta=2):
    def str_tree_1(indent,atree):
        if atree == None:
            return ''
        else:
            answer = ''
            answer += str_tree_1(indent+indent_delta,atree.right)
            answer += indent*indent_char+str(atree.value)+'\n'
            answer += str_tree_1(indent+indent_delta,atree.left)
            return answer
    return str_tree_1(0,atree) 

def count(t,value):
    nodes = []
    num = 0
    nodes.append(t)
    while len(nodes) > 0:
        if nodes[0] == value:
            num += 1
        next = nodes.pop(0)
        count(next,value)
    return num

我需要写一个递归函数count(其他三个函数不能改)；它传递平衡二叉树和一个值作为参数。它返回值在树中出现的次数。在下面的二叉树中，count(tree,1) 返回 1，count(tree,2) 返回 2，count(tree,3) 返回 4

..1
....3
3
....3
..2
......2
....3

我调用了以下函数

tree = list_to_tree([3, [2, None, [3, None, None]], [1, [3, None, None], None]])
print('\nfor tree = \n',str_tree(tree))
for i in irange(1,3):
    print('count(tree,'+str(i)+') = ', count(tree,i))

但它显示错误“RecursionError:比较中超出了最大递归深度”有人可以帮我修复计数功能吗？提前致谢。

Answer 1

如果仔细查看代码，您会发现您设置了一个空节点列表，并用 t 填充它，因此始终会进入 while 循环，您将始终将 t 弹出到 next 中，并且始终使用精确的值调用该函数相同的参数。这当然是无限递归。

以下是正确设置的一种简单方法:

def count(tree, number):
    if tree is None:
        return 0
    else:
        return (number == tree.value) + count(tree.left, number) \
            + count(tree.right, number)