递归到迭代 - AVL 树 - isBalanced

Question

我必须编写一个迭代算法来确定 AVL 树是否平衡。

我的第一个方法是找到一种直接的方法，但几个小时后我放弃了，所以我递归地编写了算法并尝试将其转换。

这是递归版本的源代码（用Python编写）

def isBalanced(root):
    if root == None:
        return -1

    lh = isBalanced(root.left)
    rh = isBalanced(root.right)

    if lh == -2 or rh == -2:
        return -2

    if abs(lh - rh) > 1:
        return -2

    return max(lh, rh) + 1

我现在的问题是，我无法转换它，也许你们中的一个人可以给我提示或解决我的问题

提前致谢

Answer 1

请记住，递归程序使用调用堆栈。您可以使用堆栈将任何递归程序转换为迭代程序。在下面的代码中，我使用了两个。

def isBalanced(root):
    nodes = [root]
    results = []
    while nodes:
        node = nodes.pop()
        if node is None:
            results.append(-1)
        else if node == 0: # 0 is a flag we use for when we are ready to combine results
            lh = results.pop()
            rh = results.pop()
            if abs(lh - rh) > 1:
                return -2  # we could have continued with the stack; this is just a shortcut
            else:
                results.append(max(lh, rh) + 1)
        else:
            nodes.push(0)
            nodes.push(node.left)
            nodes.push(node.right)
    return results, # results will have only one value

这里stack是要检查的节点堆栈以及这些节点的结果。