后序非递归遍历算法代码

后序非递归遍历，也称为层次遍历（Level Order Traversal），主要用于树形数据结构的访问，特别是二叉树。它按照“左-右-根”的顺序访问每个节点。由于不是通过函数调用栈来实现的，所以避免了递归带来的函数调用开销。

以下是使用Python实现二叉树后序遍历的非递归版本，通常会借助一个队列来辅助：

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def postorder_traversal(root):
    if not root:
        return []

    stack = [root]
    output = []
    while stack:
        node = stack.pop()
        output.append(node.val)  # 先访问当前节点
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)  # 将右子节点先压入栈，保证左子节点先出栈

    return output[::-右-根，所以我们反转结果

# 使用示例
# 假设有一个二叉树结构
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(postorder_traversal(root))  # 输出：[4, 5, 2, 3, 1]