You need to enable JavaScript to run this app. Python自定义Tree类如何正确计算树最大深度并修正错误depth函数
优惠活动
大模型
产品
解决方案
定价
更多

Python自定义Tree类如何正确计算树最大深度并修正错误depth函数

核心问题定位

你的现有代码存在两处逻辑错误,直接导致计算结果失真:

  • 递归返回值完全未被利用:你执行depth(child)后直接丢弃了子树深度的计算结果,没有将其纳入当前节点的深度统计
  • 累加规则不符合“最大深度”的定义:你在遍历每个子节点时盲目给计数加1,既没有对比取所有子树的深度最大值,还错误累加了并列子节点的贡献——比如根节点下如果有3个无后代的叶子节点,按现有逻辑会算出4层的结果,和实际2层的真实深度完全相悖
修正逻辑

树的最大深度计算遵循标准递归规则:

  • 无任何子节点的叶子节点,自身深度为1(代表当前所在层)
  • 非叶子节点的总深度 = 1 + 所有子节点对应子树的最大深度
修正后的代码

通用可读性版本

def depth(tree):
    # 初始深度为当前节点自身的1层
    current_depth = 1
    if len(tree.children) > 0:
        # 收集所有子树的深度值
        child_depth_list = []
        for child in tree.children:
            child_depth_list.append(depth(child))
        # 当前节点深度 = 自身1层 + 子树最大深度
        current_depth += max(child_depth_list)
    return current_depth

简洁精简版本

def depth(tree):
    # 叶子节点直接返回深度1
    if not tree.children:
        return 1
    # 非叶子节点直接递归计算最大子树深度,加1即为当前节点深度
    return 1 + max(depth(child) for child in tree.children)
效果验证

以一棵实际深度为3的三层树为例:

  • 第1层:根节点
    • 第2层:子节点A、子节点B
      • 第3层:孙节点A1(A的子节点)
        代入修正后函数计算:
  1. 叶子节点A1、B的返回值均为1
  2. 子节点A的深度为1 + 1 = 2
  3. 根节点的深度为1 + max(2, 1) = 3,和实际最大深度完全匹配

内容的提问来源于stack exchange,提问作者weak_at_math

相关产品推荐
方舟 Agent Plan

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

最近更新时间:2026.11.02 12:24:02