Python中树的中序遍历返回一个列表

Question

我学会了实现二叉搜索树的中序遍历：

def inorder(root): # root has val, left and right fields
    if root==None:
        return

    inorder(root.left)
    print(root.val)
    inorder(root.right)

现在，问题是我不想要控制台输出。我想获取列表中的值。我找不到让函数返回列表的方法。

我试过了，s = [inorder(root)]但没有用。

所以，我的问题是：

1. 任何方式都可以在 inorder 函数内完成，即它应该返回一个列表而不仅仅是打印值。

2. 是否有一些通用方法可以使递归函数返回数据结构，而不仅仅是将打印输出到控制台？

Answer 1

您可以递归地建立列表。只需将左右树返回的列表与当前节点中的值相加即可。

def inorder(root):
    if root==None:
        return []

    left_list = inorder(root.left)
    right_list = inorder(root.right)
    return left_list + [val] + right_list