二叉树的非递归遍历py

二叉树的非递归遍历可以使用栈来实现。具体步骤如下：

1. 新建一个栈，将根节点入栈；
2. 循环执行以下步骤，直到栈为空：
1. 弹出栈顶节点并访问它；
2. 如果该节点有右子节点，则将右子节点入栈；
3. 如果该节点有左子节点，则将左子节点入栈。

下面是实现二叉树的前序、中序和后序遍历的非递归代码示例：

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

def preorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    stack, res = [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

def inorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    stack, res = [], []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        res.append(node.val)
        node = node.right
    return res

def postorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    stack1, stack2, res = [root], [], []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    while stack2:
        res.append(stack2.pop().val)
    return res

其中，前序遍历使用一个栈来存储未处理的节点，中序遍历使用两个栈来存储未处理的节点和已处理的节点，后序遍历也使用两个栈来存储未处理的节点和已处理的节点。