如何在Python中通过递归DFS枚举非二叉树父节点的子节点系数

问题背景 #

我有一棵非二叉树，结构如下：
A包含3个子节点B（系数2）、C（系数2）、D（系数1）；B包含1个子节点E（系数4）；C包含2个子节点F（系数4）、G（系数1）；F包含1个子节点E（系数1）；G包含3个子节点D（系数1）、E（系数1）、H（系数1）。

关键说明 #

• 系数定义：仅指1个父节点包含的子节点变量数量，父节点自身的系数与此定义无关。
• 树的特性：结构随机，父节点可以有任意数量的子节点，不同父节点可以包含相同的子节点（例如F和B都包含E，数量分别为1和4）。

用字典实现该结构如下：

dicts = {
    "A": {"B":2, "C":2, "D":1},
    "B": {"E":4},
    "C": {"F":4, "G":1},
    "F": {"E":1},
    "G": {"D":1, "E":1, "H":1}
}

需求目标 #

将每个父节点仅用底层子节点（即没有子节点的E、D、H）表示，数学逻辑是遍历到底层节点后，将路径上的系数累乘，再把同一底层节点的系数相加。例如：

• A的E系数：2(B)*4(E) + 2(C)*4(F)*1(E) + 2(C)*1(G)*1(E) = 8 + 8 + 2 = 18
• A的D系数：1(D) + 2(C)*1(G)*1(D) = 1 + 2 = 3
• A的H系数：2(C)*1(G)*1(H) = 2

现有问题 #

我尝试用递归实现，但当前脚本只能正确遍历前几条分支，处理复杂结构时需要增加大量条件，且代码在计算出{A:{E:16}}后进入无限循环。现有代码如下：

dicts = {str:{str:int}}
dicts["A"] = {"B":2,"C":2,"D":1}
dicts["B"] = {"E":4}
dicts["C"] = {"F":4, "G":1}
dicts["F"] = {"E":1}
dicts["G"] = {"D":1,"E":1,"H":1}

nullvalues = ["E","D","H"]

tempIntArray = []
tempCheckedArray = {str:[str]}
tempAnsweredArray = {str:{str:int}}
persistentN = ""

def recursive_traversal(n):
    global persistentN
    if persistentN == "":
         persistentN = n
    for x in dicts[n]:
        if n not in tempCheckedArray.keys() or x not in tempCheckedArray[n]:
            if x in nullvalues:
                product = 1
                tempIntArray.append(dicts[n][x])
                for a in tempIntArray:
                    product = a * product
                if persistentN in tempAnsweredArray.keys():
                    if x in tempAnsweredArray[persistentN].keys():
                        tempValue = tempAnsweredArray[persistentN][x] + product
                        tempAnsweredArray[persistentN][x] = tempValue
                    else:
                        tempAnsweredArray.update({persistentN:{x:product}})
                else:
                    tempAnsweredArray.update({persistentN:{x:product}})

                product = 1
                if persistentN not in tempCheckedArray.keys():
                    tempCheckedArray[persistentN] = [n]
                else:
                    tempCheckedArray[persistentN].append(n)
                tempIntArray.clear()
                return recursive_traversal(persistentN)
            else:
                tempIntArray.append(dicts[n][x])
                return recursive_traversal(x)
           

recursive_traversal("A")
print(tempAnsweredArray)

我考虑过添加路径检查避免重复，但总觉得这不是最优方案，想问是否需要在递归中嵌套更多条件，还是应该换一种思路？

解决方案 #

问题根源 #

你的现有代码问题在于：

1. 使用全局变量导致状态混乱，递归过程中tempIntArray、persistentN等全局变量无法正确跟踪不同路径的系数。
2. 递归中使用return提前终止循环，导致父节点的子节点无法被完整遍历。
3. 路径检查逻辑不合理，导致重复遍历或遗漏节点，最终触发无限循环。

正确思路：递归+结果合并 #

不需要复杂的路径检查，而是让每个递归函数返回当前节点展开为底层节点的系数字典，然后父节点将子节点的结果按系数相乘后合并。具体逻辑：

1. 如果当前节点是底层节点，返回自身的系数字典（比如E返回{"E":1}）。
2. 如果当前节点有子节点，遍历每个子节点：
   • 递归获取子节点的底层系数字典。
   • 将子节点的每个系数乘以当前父节点到该子节点的系数。
   • 把这些结果合并到当前节点的结果字典中（相同底层节点的系数相加）。

实现代码 #

dicts = {
    "A": {"B":2, "C":2, "D":1},
    "B": {"E":4},
    "C": {"F":4, "G":1},
    "F": {"E":1},
    "G": {"D":1, "E":1, "H":1}
}
# 底层节点：没有子节点的节点，也可以通过判断是否在dicts的key中来自动识别
leaf_nodes = {"E", "D", "H"}

def expand_node(node):
    # 如果是底层节点，返回自身的系数字典
    if node in leaf_nodes:
        return {node: 1}
    
    result = {}
    # 遍历当前节点的所有子节点
    for child, coeff in dicts[node].items():
        # 递归展开子节点
        child_expanded = expand_node(child)
        # 将子节点的结果乘以当前系数，并合并到结果中
        for leaf, leaf_coeff in child_expanded.items():
            total_coeff = coeff * leaf_coeff
            if leaf in result:
                result[leaf] += total_coeff
            else:
                result[leaf] = total_coeff
    return result

# 测试展开节点A
print(expand_node("A"))  # 输出: {'E': 18, 'D': 3, 'H': 2}
# 也可以测试其他节点，比如C
print(expand_node("C"))  # 输出: {'E': 5, 'D': 1, 'H': 1}

优势说明 #

• 无全局变量，递归状态通过函数返回值传递，逻辑清晰。
• 自动处理任意深度和子节点数量的非二叉树结构。
• 天然避免重复计算（每个节点的展开结果只计算一次，如果需要可以加缓存优化重复调用）。

内容的提问来源于stack exchange，提问作者Runeaway3