深入遍历二叉树的各种操作详解（非递归遍历）

二叉树是计算机编程中使用最广泛的数据结构之一，它的遍历算法是二叉树操作中的重要内容。本文将介绍二叉树的深度遍历操作，包括先序遍历、中序遍历、后序遍历以及层序遍历，并提供非递归遍历的实现方法。

先序遍历

先序遍历的顺序是“根-左-右”，即先访问根节点，然后访问左子树，最后访问右子树。先序遍历适合用于创建一棵与原二叉树形状完全相同的二叉树。示例：

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

中序遍历

中序遍历的顺序是“左-根-右”，即先访问左子树，然后访问根节点，最后访问右子树。中序遍历适合用于搜索二叉树的操作，将从小到大遍历树上的所有节点。示例：

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

后序遍历

后序遍历的顺序是“左-右-根”，即先访问左子树，然后访问右子树，最后访问根节点。后序遍历适合用于二叉树中存在需要最后才能访问的节点操作。示例：

def postorder_traversal(root):
    stack = []
    res = []
    prev = None
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        node = stack[-1]
        if not node.right or node.right == prev:
            res.append(node.val)
            prev = node
            stack.pop()
        else:
            root = node.right
    return res

层序遍历

层序遍历即从上到下按层遍历，也称广度优先遍历。层序遍历需要用到队列，先将根节点加入队列，然后将队首节点取出，访问该节点的左右子节点，并将其加入队列中。示例：

def level_order(root):
    if not root:
        return []
    queue, res = [root], []
    while queue:
        level, size = [], len(queue)
        for i in range(size):
            node = queue.pop(0)
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level)
    return res