python从递归方法返回一个列表

Question

我使用本书中描述的二叉树 解决算法和数据结构问题

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

已经存在如下定义的预序遍历方法.

def preorder(tree):
    if tree:
        print(tree.self.key)
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())

我只想添加访问的节点列表的返回值.所以我可以做点什么

for i in preorder(tree):
    etc...

我无法从递归方法返回列表.一旦它到达'返回',我就尝试使用变量,递归就会停止

return [tree.self.key] + preorder()

要么

yield ...

有任何想法吗？

Answer 1

你确定要的,tree.self.key而不是简单的tree.key打印时间吗？

否则,使用yield from(Python 3.3+)的解决方案:

def preorder(tree):
    if tree:
        yield tree
        yield from preorder(tree.getLeftChild())
        yield from preorder(tree.getRightChild())

或者简单yield:

def preorder(tree):
    if tree:
        yield tree
        for e in preorder(tree.getLeftChild()):
            yield e
        for e in preorder(tree.getRightChild()):
            yield e

注意,使用函数yield或yield from将函数转换为生成函数 ; 特别是,如果你想要一个实际的列表(例如用于索引,切片或显示),你需要明确地创建它:list(preorder(tree)).

如果你有不同数量的孩子,它很容易适应:

def preorder(tree):
    if tree:
        yield tree
        for child in tree.children:
            yield from preorder(child)