二叉树后序遍历的迭代方法

Question

我写了一个递归的方法来遍历二叉树的后序遍历，代码如下。

from collections import namedtuple
from sys import stdout

Node = namedtuple('Node', 'data, left, right')
tree = Node(1,
            Node(2,
                 Node(4,
                      Node(7, None, None),
                      None),
                 Node(5, None, None)),
            Node(3,
                 Node(6,
                      Node(8, None, None),
                      Node(9, None, None)),
                 None))


def printwithspace(i):
    stdout.write("%i " % i)


def postorder(node, visitor = printwithspace):

    if node:
        print "%d-->L"%node.data
        postorder(node.left, visitor)
        print "%d-->R"%node.data
        postorder(node.right, visitor)
        print "Root--%d"%node.data

    else:
        print "Null"

stdout.write('\n postorder: ')
postorder(tree)

stdout.write('\n')

现在，我想用一种迭代的方法来实现二叉树的后序遍历，谁能帮我一下吗？

提前谢谢大家。

Answer 1

这是代码

def postorder_traverse(root):
    result = []
    list = [] #simply use list to mimic stack
    visited_node = None
    cur_node = root

    while len(list) > 0 or cur_node is not None:
        if cur_node is not None:
            #remember the middle node by "pushing" it to the stack
            list.append(cur_node)
            cur_node = cur_node.left
        else:
            middle_node = list[len(list)-1]
            #visit the middle node only if the right node is none
            #or the right node is already visited
            if middle_node.right is None or visited_node == middle_node.right:
                #visit the middle node
                result.append(middle_node.data)
                visited_node = list.pop(len(list)-1)
            else:
                #else, move to right
                cur_node = middle_node.right
    return result

Answer 2

下面的代码应该可以正常运行。简单来说，你是用一个栈来进行深度优先搜索，查找节点。同时，你还会用第二个栈来记录每个节点是否已经被扩展过。

def postorder_iteratively(node):
    stack = [node]
    expanded = [False]
    while stack:
        while stack and not stack[-1]:          #remove "non-existent" nodes from the top
            stack = stack[:-1]
            expanded = expanded[:-1]
        if stack and not expanded[-1]:          #expand node
            stack += [stack[-1].right, stack[-1].left]
            expanded[-1] = True
            expanded += [False, False]
        elif stack and expanded[-1]:            #if node has been expanded already, print it
            print stack[-1].data
            stack = stack[:-1]
            expanded = expanded[:-1]