python之"Not in function"递归函数错误

我正在编写一个算法来计算一棵树的节点总数。这是代码:

def tree_nodes(tree): 
    """Given a tree, returns the total amount of nodes it has.""" 
    def recursive_node_count(node): 
        """Recursive count function.""" 
        childs = tree[node] 
        if childs == None: 
            return 1 
        else: 
            nodes_so_far = 0 
            for i in xrange(len(childs)): 
                nodes_in_this_branch = recursive_node_count(childs[i]) 
                nodes_so_far += nodes_in_this_branch           
            return nodes_so_far 
 
    root = tree['root'] 
    total_nodes = recursive_node_count(root) 
    return total_nodes 

树 基本上是一个列表字典。示例:

tree = {0: [1], 1: [2], 2: [3, 4], 3: None, 4: None, 'root': 0} 

当我尝试运行我的代码时，这是我收到的输出:

at Answer.py. not in a function on line 31 
at Answer.py. in recursive_node_count on line 31 
at Answer.py. in recursive_node_count on line 31 
at Answer.py. in recursive_node_count on line 31 
at Answer.py. in recursive_node_count on line 31 
at Answer.py. in recursive_node_count on line 31 
at Answer.py. in recursive_node_count on line 31 
at Answer.py. in recursive_node_count on line 31 
at Answer.py. in recursive_node_count on line 31 
at Answer.py. in recursive_node_count on line 31 
at Answer.py. in tree_nodes on line 36 
at Answer.py. in <module> on line 96 

这些是行 31(在函数定义内)、36(也在定义内)和 96(调用定义)在原始代码中:

31: nodes_in_this_branch = recursive_node_count(childs[i]) 
36: total_nodes = recursive_node_count(root) 
96: nodes = tree_nodes(tree) 

我检查了语法、缩进、制表符、空格，但找不到错误。我是 Python 的初学者。你们能帮帮我吗？

请您参考如下方法:

您当前的代码有两个问题，

1. 你目前不计算根节点
2. 当没有 child 时返回 1，在这种情况下应该返回 0。我们同样需要计算每个级别的 child 数量，因此 nodes_so_far 应该用 child 列表的长度初始化

更正这些，函数变为:

def tree_nodes(tree): 
    """Given a tree, returns the total amount of nodes it has.""" 
    def recursive_node_count(node): 
        """Recursive count function.""" 
        childs = tree[node] 
        if childs == None: 
            return 0 # There are no child so return 0 in base case 
        else: 
            nodes_so_far = len(childs) # set to number of nodes passed 
            for i in xrange(len(childs)): 
                nodes_in_this_branch = recursive_node_count(childs[i]) 
                nodes_so_far += nodes_in_this_branch           
            return nodes_so_far 
    root = tree['root'] 
    total_nodes = 1 + recursive_node_count(root) # Add 1 to count the root node 
    return total_nodes 

在空运行中，这给出了输出:

>>> tree = {0: [1], 1: [2], 2: [3, 4], 3: None, 4: None, 'root': 0} 
>>> tree_nodes(tree) 
5