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

Question

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

代码如下：

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

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

我将 current 重命名为 node，将 current1 重命名为 last（对于 last printed），删除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 与处理左右子树的点之间的联系并不那么清楚。

我会使用带有状态标志的单个堆栈来跟踪您在流程中的位置：

def postorder_iterative(self):
    new, left_done, right_done = range(3)   # status of node
    stack = [[self, new]]  # node, status

    while stack:
        node, status = stack[-1]
        if status == right_done:
            stack.pop()
            print(node.key)
        else:
            stack[-1][1] += 1 # from new -> left_done and left_done -> right_done
            # new -> add left child, left_done -> add right child
            next_node = [node.leftChild, node.rightChild][status]
            if next_node is not None:
                stack.append((next_node, new))

节点会经历三种状态，只需递增状态标志即可。它们从 new 节点开始，然后进展到 left，然后是 right，当顶部堆栈处于最后一个状态，我们将其从堆栈中删除并打印节点值。

当仍处于 new 或 left 状态时，我们将左节点或右节点（如果存在）作为新节点。

另一种方法是在当前节点之前将右边的树压入堆栈。然后稍后，当你 return 到当前节点，从堆栈中取出它时，你可以检测到你仍然需要处理右侧的情况，因为堆栈的顶部将有右侧节点。在这种情况下，您将堆栈的顶部与当前节点交换并从那里继续；你稍后会 return 到同一个地方，并且不会再有堆栈顶部的右侧节点，所以你可以打印：

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 = node.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

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

Iterative postorder traversal of a binary tree with a single stack, how to approach the problem?

python

iteration

tree-traversal

binary-search-tree

postorder