将树转化为列表-迭代与递归

Question

这是我几个月前在cs考试中写的一道题，在中得了零分。我们有一个如下构建的二叉树结构：

class Tree:
def __init__(self,left=None, value=None, right=None):
if value == None or left == None or right == None:
self.empty = True
else:
self.empty = False
self.value = value
self.left = left
self.right = right

然后给出了一个从树中提取值并将其倒入列表的函数：

def to_list(self):
if self.empty:
return []
else:
ll = self.left.to_list()
lr = self.right.to_list()
return ll + [self.value] + lr

重要的是，此函数保留了在树中表示的元素顺序。

然后的任务是编写这个"；to_list"也保留此结构的函数。

从那以后，我写了一个正常运行的版本，但它非常糟糕，所以我希望有更多知识渊博的程序员参与。

这是我的版本：

def to_list_iter(self):
stack = []
if self.empty:
return []
else:
stack.append(self)
while True:
for x in range(len(stack)):
if type(stack[x]) != int:
middle = stack[x]
if middle.empty == False:
stack[x] = middle.value
stack.insert(x,middle.left)
stack.insert(x+2,middle.right)
else:
stack[x] = 0

check = True
for z in stack:
if type(z) != int:
check = False
if check == True:
return list(filter(lambda a: a != 0, stack))

Answer 1

老实说，我不完全理解你的方法是如何工作的。。。这似乎奏效了，但肯定有点复杂。while中的两个for循环看起来像O(n²(，甚至可能是O(n³(，因为循环中的insert位，而O(n(算法是可能的。

基本上，您可以在具有混合元素的堆栈上将递归转换为DFS循环：Tree节点和值(int，或Tree以外的任何类型(。从stack上的self开始，检查堆栈上的顶部元素：

• 如果它是Tree节点，而不是empty，则将right、value和left按顺序放入堆栈中；如果是empty，跳过它
• 如果是任何其他类型，则必须是value，因此将其添加到result列表中

这是有效的，因为你把left分支放在最后一个堆栈上，所以它是pop的下一个分支，因此下降到最左边的分支，然后加上它的值，然后继续它的right分支，以此类推，直到你在堆栈最底部的最右边的分支结束。

在代码中，这可能看起来有点像这样：

def to_list_iter(self):
result = []
stack = [self]
while stack:
node = stack.pop()
if isinstance(node, Tree):
if not node.empty:
stack.append(node.right)
stack.append(node.value)
stack.append(node.left)
else:
result.append(node)
return result