代码之家 › 专栏 › 技术社区 › mourinho

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

binary-search-tree data-structures recursion algorithm python

mourinho · 技术社区 · 7 年前

我学习了如何实现二进制搜索树的有序遍历:

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)] 但它不起作用。

所以,我的问题是:

这可以在inorder函数内部完成,也就是说,它应该返回一个列表,而不仅仅是打印值。
是否有一些通用的方法可以让递归函数返回数据结构,而不仅仅是将打印输出到控制台?

4 回复 | 直到 7 年前

Shaido MadHadders 7 年前

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

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

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

Udayraj Deshmukh 7 年前

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

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 )

Soham Shah 4 年前

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, [])

快乐编码:)

Bhuwan Sitaula 4 年前

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

现在,在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)