二叉树的遍历非递归算法

二叉树的遍历非递归算法可以使用栈来实现。具体来说，对于前序遍历，我们先将根节点入栈，然后每次从栈中取出一个节点，访问它的值，并将其右子节点和左子节点依次入栈；对于中序遍历，我们先将根节点入栈，然后每次从栈中取出一个节点，如果它有左子节点，则将其左子节点入栈，否则访问该节点的值并将其右子节点入栈；对于后序遍历，我们需要记录上一个访问的节点，以便在访问完一个节点的左右子节点后再访问该节点本身。具体实现可以参考下面的代码：

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 = [], []
    while stack or root:
        if root:
            stack.append(root)
            root = root.left
        else:
            node = stack.pop()
            res.append(node.val)
            root = node.right
    return res

def postorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    stack, res, last_visited = [], [], None
    while stack or root:
        if root:
            stack.append(root)
            root = root.left
        else:
            peek = stack[-1]
            if peek.right and peek.right != last_visited:
                root = peek.right
            else:
                res.append(peek.val)
                last_visited = stack.pop()
    return res