如何在不使用递归、栈或Morris遍历的前提下迭代中序遍历AVL树

AVL树本质是自平衡二叉搜索树，我们可以利用BST的后继节点特性，结合AVL的平衡属性（保证每次后继查找的时间是O(log n)），实现完全符合你要求的遍历——不用递归、栈，也不修改树结构。

核心思路很简单：从树的最左节点（中序遍历的第一个节点）开始，逐个找到当前节点的后继节点并访问，直到所有节点都被遍历完。

1. 定位遍历起点 #

中序遍历的第一个节点必然是树的最左节点，也就是从根节点一路往左走，直到没有左子节点为止：

def get_leftmost(node):
    while node.left:
        node = node.left
    return node

2. 查找后继节点 #

对于BST中的节点，后继是比它大的最小节点，分两种情况处理：

• 如果当前节点有右子树，后继就是右子树的最左节点（和找起点的逻辑一样）。
• 如果没有右子树，就得从根节点重新往下找：记录第一个比当前节点大的祖先节点，这个节点就是后继——因为BST中，所有比当前节点大的节点里，这个祖先就是最小的那个。

代码实现（假设节点包含key、left、right三个属性）：

def get_successor(root, curr):
    successor = None
    temp = root
    while temp:
        if curr.key < temp.key:
            successor = temp
            temp = temp.left
        elif curr.key > temp.key:
            temp = temp.right
        else:
            break  # 找到当前节点，停止遍历
    # 优先处理有右子树的情况
    if curr.right:
        return get_leftmost(curr.right)
    return successor

3. 完整遍历流程 #

把上面两个部分拼起来，从最左节点开始，循环访问节点并找后继，直到后继为空：

def avl_inorder_traversal(root):
    if not root:
        return []
    result = []
    curr = get_leftmost(root)
    while curr:
        result.append(curr.key)
        curr = get_successor(root, curr)
    return result

补充说明 #

• 时间复杂度：每个节点的后继查找是O(log n)，n个节点总时间是O(n log n)，虽然比栈实现的O(n)稍慢，但完全满足你的约束条件。
• 空间复杂度：只用了几个临时变量，属于O(1)的额外空间，没有用栈、递归栈，也没修改树的任何结构。
• 为什么AVL树适用？因为AVL是平衡的，每次从根找后继的时间稳定在O(log n)，不会出现退化成链表的情况，保证了效率。

内容的提问来源于stack exchange，提问作者Iulian Bodea