Python实现二叉搜索树逐层求和 现有代码无法添加根节点值如何解决
问题分析
你的现有代码存在三处核心问题,导致无法得到正确的逐层求和结果:
- 未统计根节点的数值,导致第一层结果缺失
- 仅当节点同时存在左右子节点时才计算子节点和,漏了只有单个子节点的场景
- 没有记录当前遍历的层数,无法将同层所有节点的数值累加到列表的对应位置
解决方案
提供两种可直接运行的实现方式:
方案1:层序遍历(BFS,更适合逐层处理场景)
利用队列按层遍历节点,直接统计每层总和,逻辑直观不易出错:
from collections import deque def sommaperlivelli(root): res = [] if not root: return res q = deque([root]) while q: level_sum = 0 level_size = len(q) # 遍历当前层所有节点 for _ in range(level_size): node = q.popleft() level_sum += node.key # 子节点加入队列留待下一层处理 if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level_sum) return res
方案2:修改原递归逻辑
在递归参数中增加层数标记,按层累加数值:
def sommaperlivelli(p, lista=None, livello=0): # 初始化结果列表,避免默认参数的可变对象陷阱 if lista is None: lista = [] if p is None: return lista # 首次遍历到当前层时,先添加初始值0 if len(lista) == livello: lista.append(0) # 累加当前节点值到对应层的总和 lista[livello] += p.key # 递归处理左右子节点,层数+1 sommaperlivelli(p.left, lista, livello + 1) sommaperlivelli(p.right, lista, livello + 1) return lista
测试验证
使用你提供的主函数逻辑直接调用即可:
p = NodoABR(24) p = inserisciNodo(p, 14) p = inserisciNodo(p, 27) p = inserisciNodo(p, 11) p = inserisciNodo(p, 20) p = inserisciNodo(p, 12) p = inserisciNodo(p, 55) print(sommaperlivelli(p))
运行后输出结果为 [24, 41, 98],符合要求。
内容的提问来源于stack exchange,提问作者Fail_Coder
相关产品推荐
相关产品推荐

