Python中按顺序遍历树返回列表

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

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

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

您可以传递一个列表,然后将值附加到其中,如下所示-

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

    inorder(root.left)
    ans.append(root.val)
    inorder(root.right)
ans=[]
inorder(root,ans)
print(ans)

回答您的第二个问题 :

传递数据结构本身是最简单的解决方案。如果确实希望函数“返回”输出, 一种方法是按照@Shaido的建议使用列表串联,但由于在每次递归调用时都不必要地创建一个新的单例列表,因此它的内存稍重。

更好的解决方案是使用一些静态列表(即只声明一次的固定列表)。但它不能直接在python中使用,因为python建议通过在类中声明它来实现。( A good discussion here )

def inorder(root, arr):

    if root is None:
        return
    arr.append(root.val)
    traverse(root.left, arr)
    traverse(root.right,arr)
    return arr


inorder_list = inorder(root, [])

快乐编码:)

不久前我也遇到过类似的问题。我想到的一个解决方法是创建一个实用函数,在其中传递一个列表。此列表将在递归完成时填充。

现在,在main函数中,只需使用根节点和空列表作为参数调用实用程序函数。我希望这会有所帮助。干杯

def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        self.preorder(root, result)       
        return result
    
def preorder(self, node, arr):
        if not node:
            return
        arr.append(node.val)
        self.preorder(node.left, arr)
        self.preorder(node.right, arr)