二叉树后序遍历的迭代过程

Question

我用python编写了二叉树后序遍历的递归过程。这是密码。在

^{1}$

现在，我想在PYTHON中为二叉树后序遍历执行一个迭代过程。有人能帮忙吗？在

提前谢谢。在

Answer 1

下面的代码应该可以工作。基本上，使用堆栈对节点进行深度优先搜索。 另外，您还有一个第二个堆栈，它并行地存储一个节点是否已经被扩展。在

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]

Answer 2

这是密码

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