用非递归实现二叉树的前序、中序、后序遍历算法。 注意：非递归算法写前序、中序、后序遍历算法

二叉树的非递归遍历算法通常借助栈来实现。下面分别给出二叉树的前序、中序、后序非递归遍历算法：

1. 前序遍历算法

前序遍历顺序为：根节点 -> 左子树 -> 右子树。

算法流程：

1. 如果根节点不为空，将根节点入栈。
2. 取出栈顶节点，输出该节点的值。
3. 如果该节点的右子节点不为空，将右子节点入栈。
4. 如果该节点的左子节点不为空，将左子节点入栈。
5. 重复步骤2~4，直到栈为空。

Python代码实现：

def preorderTraversal(root):
    if not root:
        return []
    res = []
    stack = [root]
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

2. 中序遍历算法

中序遍历顺序为：左子树 -> 根节点 -> 右子树。

算法流程：

1. 将根节点入栈。
2. 如果当前节点不为空，将其左子节点入栈，直到左子节点为空。
3. 取出栈顶节点，输出该节点的值。
4. 将栈顶节点的右子节点入栈。
5. 重复步骤2~4，直到栈为空。

Python代码实现：

def inorderTraversal(root):
    if not root:
        return []
    res = []
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        res.append(node.val)
        node = node.right
    return res

3. 后序遍历算法

后序遍历顺序为：左子树 -> 右子树 -> 根节点。

算法流程：

1. 将根节点入栈。
2. 如果当前节点不为空，将其左子节点入栈，直到左子节点为空。
3. 如果当前节点的右子节点为空或者已经被访问过，输出该节点的值，并将其出栈。
4. 标记当前节点已被访问。
5. 将当前节点的右子节点入栈。
6. 重复步骤2~5，直到栈为空。

Python代码实现：

def postorderTraversal(root):
    if not root:
        return []
    res = []
    stack = [(root, False)]
    while stack:
        node, visited = stack.pop()
        if not node:
            continue
        if visited:
            res.append(node.val)
        else:
            stack.append((node, True))
            stack.append((node.right, False))
            stack.append((node.left, False))
    return res