发现了一个错误，修复了它，我不明白为什么它会被窃听？

Question

我遇到了一个错误，现在已经修复了，但我仍然不明白它的根本原因。

我想做的事情：

使用 post-order 树遍历从二叉树中得到 postfix 表达式。该表达式将被 returned 作为列表对象，例如：给出

的表达式树

"((a+1)+1)"

我希望我的函数 return 以下列表：

 ["a","1","+","1","+"]

我遇到的问题：

连续多次使用我的函数（称为 postfix）只是 "adds" 最新列表到以前的列表。给定

的表达式树，这就是我的意思

"((a+1)+1)"

写作

 postfix( BinaryTree of "((a+1)+1)")

将return

 ["a","1","+","1","+"]

并在同一棵树上再次调用该函数将 return

["a","1","+","1","+","a","1","+","1","+"]

有人可以向我解释为什么会这样吗？这是我的其余代码

class BinaryTree:
    def __init__(self,rootVal,leftBinaryTree=None,rightBinaryTree=None):
        self.key = rootVal
        self.left = leftBinaryTree
        self.right = rightBinaryTree
    def getRootVal(self):
        return self.key
    def getLeftChild(self):
        return self.left
    def getRightChild(self):
        return self.right

""" Tree Traversal """


def postorder(tree):
    if tree != None:
        postorder(tree.getLeftChild())
        postorder(tree.getRightChild())
        print(tree.getRootVal())

""" posfix from tree """                         


def postfix(tree,stack = []):
    if tree!=None:
        postfix(tree.getLeftChild(),stack)
        postfix(tree.getRightChild(),stack)
        stack.append(tree.getRootVal())
    return stack

expression = "((a+1)+1)"
tree = BinaryTree("+",BinaryTree("+",BinaryTree("a"),BinaryTree("1")),BinaryTree("1"))

print(postfix(tree))
print(postfix(tree))
print(postfix(tree))

输出如下

['a', '1', '+', '1', '+']
['a', '1', '+', '1', '+', 'a', '1', '+', '1', '+']
['a', '1', '+', '1', '+', 'a', '1', '+', '1', '+', 'a', '1', '+', '1', '+'

我在写这篇文章时发现明确使用

postfix(tree,[])

似乎可以解决问题。谁能告诉我问题出在哪里，这样我以后就可以避免它了？

Answer 1

在对 postfix() 的所有 3 次调用中，

stack[] 都存在于内存中。因此，每次您使用 append() 时，它只是将根添加到堆栈列表中。

如果您观察输出的第 2 行和第 3 行，这很明显。'a'、'1'、'+'、'1'、'+' 在第一行出现一次，在第二行出现两次第二次和第三次三次。如果您第四次再次调用该方法 'a'，'1', '+', '1', '+' 将在 stack[].

中重复 4 次

发现了一个错误，修复了它，我不明白为什么它会被窃听？

Found a bug, fixed it , I dont understand why it was bugging?

python-3.x

recursion

binary-tree

tree-traversal

postfix-notation