0

我想编写一个函数,它返回列表中树中的所有元素。我不允许使用全局变量。这是我尝试过的:

def traverse(current node):    
    if no left child and no right child:
        return current nodes data
    else:
        if both left child and right child exist:
            return [current nodes data,left_child.traverse(),right_child._traverse()]
        elif no left child:   return [current node's data,right_child.traverse()]
        elif no right child:  return [current node's data,left_child.traverse()]

我们用这个例子:(根是2,左孩子是1,右孩子是3,右孩子的右孩子是4)

    2
1      3
          4

在这棵树上调用 traverse 返回:

[2, 1, [3, 4]]

所以唯一的问题是我们不能把它全部放在一个列表中。

编辑:这里有一些可以调用的节点函数: node.data, node.left,node.right

4

2 回答 2

2

您不想返回值列表,而是希望传入一个数组并将值递归地附加到数组中:

def traverse(node, arr):
    if node.left:
        traverse(node.left, arr)
    arr.append(node.data)
    if node.right:
        traverse(node.right, arr)
    return arr # this is for convenience so we don't have to store arr

您可以通过调用以下方式获取列表:

traverse(node, [])
于 2013-04-05T03:21:23.473 回答
0

问题是每个函数调用都在创建一个新列表并将其附加到现有列表中。相反,您希望将子节点添加到现有列表中。

这是一个不依赖于在调用之间显式传递列表的递归解决方案:

def traverse(node):
    if node.left and node.right:
        return [node.data] + traverse(node.left) + traverse(node.right)
    elif node.left:
        return [node.data] + traverse(node.left)
    elif node.right:
        return [node.data] + traverse(node.right)
    else:
        return [node.data]
于 2013-04-05T03:22:36.960 回答