如何返回二叉搜索树的"in"，'pre'和'post'顺序列表？

Question

对于我的作业，我需要根据给出的字符串(in，pre和post(中的二进制树中包含正确订单的节点的列表。但是它返回'None'，我不知道怎么了。感谢您的任何帮助。

class BinarySearchTree:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
def create_new_bst(nums):
    root = None
    for num in nums:
        root = insert(root, num)
    return root
def insert (t, data):
    if not t:
        return BinarySearchTree(data)
    elif t.data == data:
        t.count += 1
    elif data < t.data:
        t.left = insert(t.left, data)
    else:
        t.right = insert(t.right, data)
    return t
def traverse(t, order):
    if order == 'in':
       return inorder(t)
    elif order == 'pre':
       return preorder(t)
    elif order == 'post':
       return postorder(t)
def inorder(root):
    lst = []
    if root: 
        inorder(root.left) 
        lst.append(root.data)
        inorder(root.right) 
    return lst
def postorder(root):
    lst = []
    if root: 
        postorder(root.left) 
        postorder(root.right) 
        lst.append(root.data)
    return lst
def preorder(root):
    lst = []
    if root: 
        lst.append(root.data)
        preorder(root.left) 
        preorder(root.right) 
    return lst
t = create_new_bst([55, 24, 8, 51, 25, 72, 78])
result = traverse(t, 'post')
print('Result =', result)

Answer 1

因此，除了构造BST的初始问题外，遍历没有从left和right子树返回的值更新lst变量。以下代码应起作用：

def inorder(root):
    lst = []
    if root:
        lst = inorder(root.left)
        lst.append(root.data)
        lst.extend(inorder(root.right))
    return lst
def postorder(root):
    lst = []
    if root:
        lst = postorder(root.left)
        lst.extend(postorder(root.right))
        lst.append(root.data)
    return lst
def preorder(root):
    lst = []
    if root:
        lst.append(root.data)
        lst.extend(preorder(root.left))
        lst.extend(preorder(root.right))
    return lst

extend是一种列表方法，将每个项目从参数列表添加到呼叫者列表的末尾。