有序遍历

Question

我正在查看一个树实现的有序递归遍历，并想知道如何将结果保存到一个列表中，然后从递归函数返回该结果。我对如何在堆栈展开期间持久化这个列表有问题。在

我的代码是：

class BinaryTreeNode(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def recursive_inorder(root):
    if not root:
        return

    nodes = list()

    recursive_inorder(root.left)
    nodes.append(root.value)
    print root.value
    recursive_inorder(root.right)
    return nodes

我称之为：

^{pr2}$

节点按正确的顺序遍历，但我很难弄清楚如何将结果保存到nodes列表中。在

Answer 1

使用递归调用的返回值扩展节点列表。另外，当您有一个None值时，返回一个空列表，这样您的函数就可以保证总是返回一个列表：

def recursive_inorder(root):
    if not root:
        return []

    nodes = list()

    nodes.extend(recursive_inorder(root.left))
    nodes.append(root.value)
    nodes.extend(recursive_inorder(root.right))
    return nodes

或者更简洁一点：

^{pr2}$