You need to enable JavaScript to run this app. Python实现二叉搜索树逐层求和 现有代码无法添加根节点值如何解决
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.14 07:24:06