Python后序遍历非递归算法

以下是Python中使用非递归算法进行后序遍历的示例代码：

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

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

    result = []
    stack = [(root, False)]

    while stack:
        node, visited = stack.pop()

        if visited:
            result.append(node.val)
        else:
            stack.append((node, True))

            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))

    return result

这段代码使用一个栈来模拟递归过程。首先，将根节点和一个标志位（用于表示是否已访问过）入栈。然后，开始循环，直到栈为空。

在每次循环中，从栈中弹出一个节点和对应的标志位。如果标志位为True，表示已经访问过该节点的子节点，将节点的值添加到结果列表中。如果标志位为False，表示还没有访问过该节点的子节点，则将节点和标志位重新入栈，并按照右子节点、左子节点的顺序入栈。

这样，通过不断迭代和入栈操作，直到栈为空，就完成了后序遍历，最后返回结果列表即可。

你可以使用以下代码创建一个示例树，并调用postorderTraversal函数进行后序遍历测试：

# 创建示例树
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)

# 进行后序遍历
result = postorderTraversal(root)
print(result)  # 输出: [3, 2, 1]