Python前序遍历非递归算法

下面是一个使用迭代实现前序遍历的非递归算法的示例：

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


def preorderTraversal(root):
    result = []  # 存储结果的列表
    stack = []  # 存储节点的栈

    if root:
        stack.append(root)

    while stack:
        node = stack.pop()
        result.append(node.val)

        # 先将右子节点入栈，再将左子节点入栈，保证左子节点先出栈
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

在这个算法中，我们使用一个栈来存储待处理的节点。首先，我们将根节点入栈。然后，进入循环，直到栈为空。在每次循环中，我们从栈中弹出一个节点，将其值添加到结果列表中。接下来，我们将右子节点入栈，再将左子节点入栈。这样可以保证在下一次循环中，左子节点会被先处理。最终，返回结果列表即可。

你可以使用以下代码来测试这个算法：

# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 调用前序遍历算法
result = preorderTraversal(root)

# 打印结果
print(result)

输出结果将会是：[1, 2, 4, 5, 3]，这是对给定二叉树进行前序遍历的结果。