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的子节点)
代入修正后函数计算:
- 第3层:孙节点A1(A的子节点)
- 第2层:子节点A、子节点B
- 叶子节点A1、B的返回值均为1
- 子节点A的深度为
1 + 1 = 2 - 根节点的深度为
1 + max(2, 1) = 3,和实际最大深度完全匹配
内容的提问来源于stack exchange,提问作者weak_at_math
相关产品推荐
相关产品推荐

