二叉树转列表：递归转迭代实现优化求助

数月前我参加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

同时给出了一个递归实现的to_list函数，它能按左子树→根节点→右子树的中序顺序提取树中元素为列表：

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))

你的实现存在的问题 #

• 效率极低：每次循环都要遍历整个栈，还频繁执行insert操作（数组插入是O(n)复杂度），树的节点越多，性能下降越明显。
• 逻辑冗余：用整数标记空节点和已处理节点，还需要额外遍历栈检查是否全部处理完成，代码可读性差。
• 健壮性不足：如果树节点的value本身是整数，会和标记的0冲突，导致错误过滤。

标准的中序遍历迭代实现方案 #

中序遍历的迭代实现核心是利用栈模拟递归调用过程，遵循先遍历左子树到底，再访问根节点，最后遍历右子树的逻辑，代码简洁且效率高：

def to_list_iter(self):
    result = []
    stack = []
    current = self
    
    while current.empty is False or stack:
        # 遍历到左子树最底层
        while current.empty is False:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        # 访问根节点
        result.append(current.value)
        # 转向右子树
        current = current.right
    
    return result

方案说明 #

1. 初始化：用result存储最终遍历结果，stack保存待访问节点，current指向当前处理的节点。
2. 左子树遍历：循环将当前节点压入栈，直到左子树为空。
3. 访问根节点：弹出栈顶节点（最底层左节点或根节点），将其值加入结果列表。
4. 处理右子树：将current指向弹出节点的右子树，重复上述过程。
5. 终止条件：当当前节点为空且栈为空时，遍历完成。

这个实现的时间复杂度是O(n)（每个节点入栈出栈各一次），空间复杂度是O(h)（h为树的高度），远优于你之前的实现，同时逻辑清晰，可读性强，也不会出现值冲突的问题。

内容的提问来源于stack exchange，提问作者PeterPefi