python - 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

Are you sure you want tree.self.key and not simply tree.key when you print?

Otherwise, a solution with yield from (Python 3.3+):

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

Or with simple yield:

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

Note that using yield or yield from transforms the function into a generator function; in particular, if you want an actual list (for indexing, slicing, or displaying for instance), you'll need to explicitly create it: list(preorder(tree)).

If you have a varying number of children, it's easy to adapt:

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

Answer 2

您必须实际从递归函数返回一个值（目前，它只是打印值）。而且您应该随时构建列表，并且可能稍微清理一下代码 - 如下所示：

def preorder(tree):
    if not tree:
        return []
    # optionally, you can print the key in this line: print(self.key)
    return [tree.key] + preorder(tree.leftChild) + preorder(tree.rightChild)

Answer 3

您可以向函数添加第二个参数preorder，例如

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

...
vn = []
preorder(tree, vn)

Answer 4

您可以简单地为每个递归调用返回一个连接列表，它结合了当前键、左子树和右子树：

def preorder(tree):
        if tree:
            return ([tree.key] + preorder(tree.getLeftChild()) +
                    preorder(tree.getRightChild()))
        return []

对于 n 叉树：

def preorder(tree):
    if tree:
        lst = [tree.key]
        for child in tree.children:
            lst.extend(preorder(child))
        return lst
    return []