Python 如何计算包含dict列表的嵌套字典的最长分支深度?
含字典列表的嵌套结构最长分支深度计算
问题说明
需要计算给定嵌套字典结构的最长分支深度,示例结构的预期最长链路为BSB1→BSB2→BSB5→BSB6→BSB8,对应深度值为5。
现有递归实现存在两个典型问题:
- 运行触发KeyError:代码中尝试访问节点不存在的
BusinessUnit字段,实际结构的节点名称字段为Name - 手动传递、累加深度计数器的逻辑,在多分支遍历场景下容易出现错误的计数偏移,无法得到预期结果
原代码问题拆解
原实现代码:
def calculate_depth(flow,depth): depth+=1 md = [] if flow['Output']: for o in flow['Output']: print(o['BusinessUnit']) md.append(calculate_depth(o,depth)) print(max(md)) print(md) return max(md) else: return depth print(calculate_depth(respons['root']['Flow'][0],0))
核心问题点:
- 残留旧字段引用:
o['BusinessUnit']是旧数据结构的遗留代码,和当前示例的字段定义完全不匹配,运行即报错 - 计数逻辑存在隐患:将深度值作为形参逐层传递累加,在多分支遍历场景下很容易出现计数偏移——比如遍历完第一个长分支后,参数没有正确回退到分支起点,会把长分支的累计值叠加到后续短分支的计数上,导致最终结果错误
修正实现
核心思路:让每个节点独立计算自身对应的深度值,不再通过外部传参维护需要累加的计数器,从根源上避免多分支遍历的计数偏移问题。
计算规则:
- 每个节点自身代表1层深度
- 如果节点存在非空的
Output子节点列表,当前节点的深度 = 1 + 所有子节点分支的最大深度 - 如果节点没有有效子节点,直接返回自身的深度值1
修正后的代码:
def calculate_depth(node): current_depth = 1 # 存在非空子节点列表时,递归计算所有子节点的深度 if node.get('Output'): child_max_depth = max(calculate_depth(child) for child in node['Output']) current_depth += child_max_depth return current_depth # 从根节点BSB1开始计算 root_node = respons['root']['Flow'][0] print(calculate_depth(root_node))
结果校验
沿最长分支逐节点计算,验证结果匹配度:
- BSB8:无有效Output,深度1
- BSB6:1 + BSB8的深度1 = 2
- BSB5:1 + max(BSB6的深度2, BSB7的深度1) = 3
- BSB2:1 + BSB5的深度3 = 4
- BSB1:1 + max(BSB2的深度4, BSB3的深度2) = 5
最终输出和预期值完全一致,整个计算过程没有手动累加的全局计数器,每个递归上下文独立计算深度,不会出现跨分支的计数错误。
内容的提问来源于stack exchange,提问作者Khalid CHBAB
相关产品推荐
相关产品推荐

