如何简洁实现单父多子图中无子女节点的查找方法？

首先明确现有数据结构：

class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.parent = None
        self.children = []

class Graph:
    def __init__(self, node) -> None:
        self.root_node = node

    def add_relationship(self, parent, child):
        if not parent.parent:
            parent.parent = self.root_node
            self.root_node.children.append(parent)

        parent.children.append(child)
        child.parent = parent

需求是为Graph类添加方法，返回图中所有没有子节点的节点。原递归实现存在返回结果重复嵌套的问题，以下是两种更简洁可靠的实现方式：

方案1：递归遍历 #

直接从根节点开始递归遍历所有节点，收集无子女的节点：

class Graph:
    # 保留原有__init__和add_relationship方法
    # ...

    def get_end_nodes(self):
        end_nodes = []
        
        def traverse(node):
            # 当前节点无子女，加入结果列表
            if not node.children:
                end_nodes.append(node)
            else:
                # 遍历所有子节点
                for child in node.children:
                    traverse(child)
        
        traverse(self.root_node)
        return end_nodes

这个实现逻辑清晰，避免了原代码中可变默认参数导致的状态残留问题，递归过程中只会收集符合条件的节点一次。

方案2：迭代式广度优先搜索（BFS） #

如果偏好非递归实现，可以用队列做广度优先遍历，同样能高效收集目标节点：

class Graph:
    # 保留原有__init__和add_relationship方法
    # ...

    def get_end_nodes(self):
        end_nodes = []
        # 初始化队列，从根节点开始
        queue = [self.root_node]
        
        while queue:
            current_node = queue.pop(0)
            if not current_node.children:
                end_nodes.append(current_node)
            else:
                # 将子节点加入队列，继续遍历
                queue.extend(current_node.children)
        
        return end_nodes

原实现问题分析 #

原代码的核心问题有两个：

1. 使用了可变默认参数（nodes_with_children=[], nodes_without_children=[]），Python中可变默认参数会在函数定义时初始化，后续调用会复用同一个列表，导致结果混乱。
2. 逻辑上错误地将无子女节点列表与递归返回结果拼接，导致最终返回嵌套的重复列表。

内容的提问来源于stack exchange，提问作者Mr. Kelsey