二叉树遍历问题模板

taixian / 2024-02-15 / 原文

在二叉树遍历问题中，有三种常见的遍历方式：前序遍历、中序遍历和后序遍历。以下是这三种遍历方式的递归模板：

1. 前序遍历（Preorder Traversal）：

def preorderTraversal(root):
    if not root:
        return []
    
    result = []
    result.append(root.val)  # 处理当前节点
    result.extend(preorderTraversal(root.left))  # 递归处理左子树
    result.extend(preorderTraversal(root.right))  # 递归处理右子树
    
    return result

2. 中序遍历（Inorder Traversal）：

def inorderTraversal(root):
    if not root:
        return []
    
    result = []
    result.extend(inorderTraversal(root.left))  # 递归处理左子树
    result.append(root.val)  # 处理当前节点
    result.extend(inorderTraversal(root.right))  # 递归处理右子树
    
    return result

3. 后序遍历（Postorder Traversal）：

def postorderTraversal(root):
    if not root:
        return []
    
    result = []
    result.extend(postorderTraversal(root.left))  # 递归处理左子树
    result.extend(postorderTraversal(root.right))  # 递归处理右子树
    result.append(root.val)  # 处理当前节点
    
    return result

这些模板基于递归思想，对二叉树进行深度优先遍历。对于每个节点，都会首先处理当前节点，然后递归处理左子树和右子树。这样可以保证在遍历过程中按照前序、中序或后序的顺序访问节点。

在实际应用中，也可以使用迭代的方法，例如使用栈来模拟递归的过程，实现非递归的遍历。

迭代法模板
以下是使用迭代法进行二叉树遍历的模板。这里使用栈来模拟递归的过程，实现非递归的遍历。

1. 前序遍历（Preorder Traversal）：

def preorderTraversal(root):
    if not root:
        return []

    result = []
    stack = [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

2. 中序遍历（Inorder Traversal）：

def inorderTraversal(root):
    if not root:
        return []

    result = []
    stack = []

    while stack or root:
        while root:
            stack.append(root)
            root = root.left  # 先一直往左走到底，模拟递归的过程

        node = stack.pop()
        result.append(node.val)  # 处理当前节点
        root = node.right  # 处理右子树，如果右子树为空，下一次循环会继续处理栈中的节点

    return result

3. 后序遍历（Postorder Traversal）：

def postorderTraversal(root):
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.insert(0, node.val)  # 插入到结果列表的开头，模拟逆序

        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return result

这些迭代法的模板使用栈来辅助遍历，通过不断地迭代，模拟了递归的过程。这样可以在不使用递归的情况下实现二叉树的前序、中序和后序遍历。

其他优秀模板链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/642769/python3-die-dai-bian-li-chang-gui-jie-fa-1egc/
https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/247053/tu-jie-er-cha-shu-de-si-chong-bian-li-by-z1m/