遍历一棵树

Question

我想写一个函数，它返回列表中树中的所有元素。尽管我不允许使用全局变量。下面是我的尝试：

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 

呼吁横向上这棵树返回此：

[2, 1, [3, 4]]

所以，唯一的问题是，我们不能把一切以适应只有一个列表中。

编辑：这里是一些节点功能，这可以被称为： node.data，node.left，node.right

Answer 1

，而不是返回值的列表，你希望在一个数组来传递和递归追加值的数组：

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

Answer 2

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

这里是一个递归的解决方案，不依赖于明确地传递调用之间的列表：

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]