迭代后序遍历二叉树的单栈问题，如何解决？

Question

我一直在研究算法和数据结构，我写了一个二叉树的后序遍历，不使用递归，只使用一个堆栈。在

代码如下：

def postorder_iterative(self):
    current = self
    s = []
    current1 = None
    done = 0
    def peek(s):
        return s[-1]

    while(not done):
        if current and (current != current1):
            s.append(current)
            current = current.leftChild
        elif(len(s) > 0):
            if peek(s).rightChild and peek(s).rightChild != current:
                current = peek(s).rightChild
            else:
                current = current1 = s.pop()
                print(current.key)
        else:
            done = 1

这个代码实际上是有效的，但我花了很多时间才想出它。在

有人能解释一下这个问题的直观思维方式吗？在

我希望能够用逻辑来重现它，而不是花那么多时间在上面。在

Answer 1

后序遍历要求只在遍历左子树和右子树后打印当前节点值。您正在使用堆栈遍历左树only，并使用current1变量（最后一个打印的节点）来知道您现在正在退出右侧树，以便可以打印当前节点。在

我将current重命名为node，current1重命名为last（对于上次打印的），删除peek()函数，只将stack[-1]直接引用为tos（栈顶），并简化方法：

def postorder_iterative(self):
    node, last = self, None
    stack = []

    while True:
        if node and node is not last:
            # build up the stack from the left tree
            stack.append(node)
            node = node.leftChild
        elif stack:
            # no more left-hand tree to process, is there a right-hand tree?
            tos = stack[-1]
            if tos.rightChild and tos.rightChild is not node:
                node = tos.rightChild
            else:
                # both left and right have been printed
                node = last = stack.pop()
                print(last.key)
        else:
            break

然而，仍然很难理解到底发生了什么，因为last与左、右子树被处理的点之间的联系并不那么清楚。在

我将使用带有状态标志的单个堆栈来跟踪进程中的位置：

^{pr2}$

节点只需增加状态标志就可以通过三种状态。它们从新的节点开始，然后前进到left，然后right，当堆栈顶部处于最后一个状态时，我们将其从堆栈中移除并打印节点值。在

当仍然处于new或left状态时，我们将left或right节点（如果存在）作为新节点添加到堆栈中。在

另一种方法是将右侧的树推送到当前节点之前的堆栈上。然后，当您从堆栈中取出当前节点后，当您返回到当前节点时，您可以检测到仍然需要处理右侧节点的情况，因为堆栈顶部将有右侧节点。在这种情况下，您将堆栈顶部与当前节点交换，并从那里继续；稍后将返回到同一位置，并且堆栈顶部不再有右侧节点，因此可以打印：

def postorder_iterative(self):
    stack = []
    node = self

    while node or stack:
        while node:
            # traverse to the left, but add the right to the stack first
            if node.rightChild is not None:
                stack.append(node.rightChild)
            stack.append(node)
            node = stack.leftChild

        # left-hand tree traversed, time to process right or print
        node = stack.pop()

        if stack and node.rightChild is stack[-1]:
            # right-hand tree present and not yet done, swap tos and node
            node, stack[-1] = stack[-1], node
        else:
            print(node.key)
            node = None