Python递归函数如何返回树中无子节点的叶子节点？

问题背景 #

你有这样一棵结构的树：

0
 / \
1   2
/ \ /|\
3 4 5 6 7

需求是通过递归函数从树对象中返回所有无子节点的叶子节点（也就是3、4、5、6、7）。你已经用传入列表收集结果的方式实现了需求，但希望改用return语句直接返回结果，尝试的代码只返回单个节点，遇到了困境。

现有可行的列表收集方案 #

你当前能用的代码是这样的（通过传入列表来收集叶子节点）：

def find(self, nodes):
    if not hasattr(self, 'children'):
        nodes.append(self)
    else:
        for i in self.children:
            i.find(nodes)

nodes = []
node.find(nodes)  # 可以传入任意节点（0、1、2、3、4等）
print(nodes)

你尝试的递归返回方案（存在问题） #

你尝试改用return返回结果，但这个函数只会返回单个节点：

def find2(self):
    if not hasattr(self, 'children'):
        return self
    else:
        for i in self.children:
            return i.find2()

nodes = root.find2()
print(nodes)

问题出在：循环里第一次遍历到子节点就直接return了，只会返回第一个子节点递归得到的第一个叶子，不会继续处理其他子节点，自然得不到所有叶子。

正确的递归返回实现 #

我们需要让每个非叶子节点收集所有子节点返回的叶子节点，然后合并起来返回。这里有两种常用的实现方式：

方式1：返回叶子节点列表 #

修改后的函数会为每个节点返回一个叶子列表，非叶子节点会把所有子节点的列表合并后返回：

def find2(self):
    # 如果是叶子节点，返回包含自身的列表
    if not hasattr(self, 'children'):
        return [self]
    else:
        leaves = []
        for child in self.children:
            # 把每个子节点返回的叶子列表合并到当前列表
            leaves.extend(child.find2())
        return leaves

调用的时候直接接收返回值即可：

nodes = root.find2()
print(nodes)

这样就能得到包含所有叶子节点的列表了。

方式2：使用生成器（内存友好） #

如果你的树很大，不想一次性生成整个列表，也可以用生成器逐个返回叶子节点：

def find_leaves(self):
    if not hasattr(self, 'children'):
        yield self
    else:
        for child in self.children:
            # 迭代子节点的生成器，逐个yield叶子
            yield from child.find_leaves()

调用时可以把生成器转换成列表：

nodes = list(root.find_leaves())
print(nodes)

这两种方式都能解决你的问题，核心是不要在循环里提前return，而是收集所有子节点的递归结果。

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