递归统计N-ary树奇数节点的Python代码错误排查求助

问题背景 #

• 题目要求：通过递归方法统计N叉树中所有值为奇数的节点总数
• 测试用例树结构如下：

5                                           
      ________|_____________                        
     |          |           |                      
     20         4           6                      
     |     _____|______                      
     11   |   |  |  |  |                    
          10  2  9  8  7                  
            __|__                        
           |     |                    
           3     1         

• 预期结果：该树共12个节点，其中奇数值节点共6个，函数应返回6
• 异常表现：编写的es7函数运行后始终返回0，无法定位错误
• 原有实现代码、节点定义与测试辅助函数如下：

def es7(tree):
    n = 0
    for element in tree.f: 
        n = es7(element)
        if element.id % 2 == 1: 
            n += 1 
    return n  
 

class Nodo:
    def __init__(self,V):
        self.id=V
        self.f=[]


################### DA QUI IN GIÙ SONO SOLO FUNZIONI NECESSARIE PER I TEST #####################

def fromLista(lista):
    '''Crea l'albero da una lista [valore, listafigli]
           In cui lista figli contiene alberi o e' la lista vuota. '''
    r=Nodo(lista[0])
    r.f=[fromLista(x) for x in lista[1]]
    return r

def toLista(nodo):
    ''' Converte l'albero in una lista di liste [valore, listafigli]'''
    return [nodo.id, [toLista(x) for x in nodo.f]]   

错误原因 #

代码存在两个核心逻辑错误：

1. 漏统计当前递归层的根节点：整个递归逻辑只遍历了节点的子节点，从未判断传入函数的当前节点（tree参数）本身的值是否为奇数，最顶层的根节点从一开始就不会被纳入计数。
2. 子树计数被覆盖而非累加：遍历子节点时，直接用n = es7(element)将n赋值为单个子树的统计结果，之前遍历过的所有子树的计数会被直接覆盖，最终n只会保留最后一个子节点的统计值，前面所有子树的结果全部丢失。

修复方案 #

调整递归逻辑：首先统计当前节点的贡献（奇数记1，偶数记0），再依次累加所有子树的递归统计结果即可，修复后的函数代码如下：

def es7(tree):
    # 先计入当前节点的计数
    n = 1 if tree.id % 2 == 1 else 0
    # 累加所有子树的奇数节点数
    for element in tree.f: 
        n += es7(element)
    return n

修复后运行测试用例，可正确统计到5、11、9、7、3、1共6个奇数节点，返回结果符合预期。

内容的提问来源于stack exchange，提问作者alex108