如何修复find_parents方法的树遍历，获取重复节点的所有父节点？

树形结构 #

├── A
│   ├── B
│   │   ├── D
│   │   └── E
│   └── C
│       ├── F
│       └── D
├── E
└── F

原代码 #

class Knoten:
    def __init__(self, wert):
        self.val = wert
        self.children = []

    # Fügt die Kindestknoten zu einem Vaterknoten hinzu
    def add_knoten(self, add_knoten):
        self.children.append(add_knoten)

    # Gibt die Struktur des Baumes aus
    def StrukturOutput(self, ebene=0):
        einruecken = " " * ebene
        print(einruecken + self.val)
        for i in self.children:
            i.StrukturOutput(ebene + 1)

    def get_leaf_nodes(self, target_val):
        if self.val == target_val:
            if len(self.children) == 0:
                return [self.val]
            else:
                leaf_nodes = []
                for child in self.children:
                    if len(child.children) == 1:  # Überprüfung, ob der Kindknoten Blattknoten ist
                        leaf_nodes.append(child.val)
                    leaf_nodes.extend(child.get_leaf_nodes(child.val))
                return leaf_nodes
        else:
            for child in self.children:
                leaf_nodes = child.get_leaf_nodes(target_val)
                if leaf_nodes:
                    return leaf_nodes
        return []

    # Gibt den Vater eines Knoten aus
    def find_parents(self, target_val, parents=None):
        if self.val == target_val:
            return parents
        if parents is None:
            parents = []
        for child in self.children:
            result = child.find_parents(target_val, parents + [self.val])
            if result is not None:
                return result
        return None
            

# Erstellt die Wurzel
baum = Knoten('A')

# Erstelleung der Kindenknoten, der Wurzel
b = Knoten('B')
c = Knoten('C')
e = Knoten('E')
f = Knoten('F')

# Erstellt die Kinderknoten des Knoten B
b1 = Knoten("D")
b2 = Knoten("E")
# Erstellt die Beziehung zwischen B und seinen Kinderknoten
b.add_knoten(b1)
b.add_knoten(b2)

# Erstellt die Kinderknoten des Knoten C
c1 = Knoten("F")
c2 = Knoten("D")
# Erstellt die Beziehung zwischen C und seinen Kinderknoten
c.add_knoten(c1)
c.add_knoten(c2)

# Beziehung zwischen Wurzel und seinen Kindern
baum.add_knoten(b)
baum.add_knoten(c)
baum.add_knoten(e)
baum.add_knoten(f)


suche = input("Insert (Tree nodes): ")

if baum.get_leaf_nodes(suche) == [suche]:
    vater = baum.find_parents(suche)
    if vater:
        print(f"Vaterknoten von {suche} sind {vater}")
else:
    kinder = baum.get_leaf_nodes(suche)
    print(f"{suche} hat folgende Kinder: {kinder}")

问题描述 #

当前find_parents方法仅能返回第一个匹配到的目标节点的父路径。例如输入D时，只会返回['A', 'B']，但实际上D存在两个父路径：['A', 'B']和['A', 'C']，需修改方法以收集所有匹配的父路径。

修改后的find_parents方法 #

def find_parents(self, target_val, parents=None):
    if parents is None:
        parents = []
    # 若当前节点是目标，返回包含当前路径的列表
    if self.val == target_val:
        return [parents.copy()]
    all_paths = []
    for child in self.children:
        # 递归遍历子节点，传递更新后的路径
        child_paths = child.find_parents(target_val, parents + [self.val])
        if child_paths:
            all_paths.extend(child_paths)
    # 返回所有收集到的路径，无匹配则返回None
    return all_paths if all_paths else None

修改说明 #

1. 新增all_paths列表用于收集所有匹配的父路径，避免找到第一个结果就终止遍历。
2. 当当前节点匹配目标时，返回包含当前路径的列表（确保每个路径作为独立元素存储）。
3. 遍历所有子节点，将每个子节点返回的路径合并到总路径列表中。
4. 最终返回所有收集到的路径，若无匹配则返回None。

修改后输入D会返回[['A', 'B'], ['A', 'C']]，符合预期；输入根节点直接子节点（如E）会返回[['A', 'B'], []]，其中空列表代表该节点为根节点的直接子节点，无上层父节点。

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