二叉树的前中后序遍历

一、二叉树遍历基础概念

二叉树的遍历是指按照某种顺序访问二叉树中的每个节点，且每个节点仅访问一次。常见的遍历方式包括前序遍历、中序遍历和后序遍历，其核心区别在于根节点、左子树和右子树的访问顺序。

遍历类型	访问顺序	适用场景
前序遍历	根节点 → 左子树 → 右子树	树的创建、表达式求值前缀表示
中序遍历	左子树 → 根节点 → 右子树	表达式求值中缀表示、排序二叉树遍历
后序遍历	左子树 → 右子树 → 根节点	释放树资源、表达式求值后缀表示

二、递归实现

递归实现基于二叉树的递归定义，代码简洁直观，利用函数调用栈自动管理遍历顺序。以下以Python语言为例：

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

# 前序遍历递归实现
def preorderTraversal_recursive(root):
    if not root:
        return []
    return [root.val] + preorderTraversal_recursive(root.left) + preorderTraversal_recursive(root.right)

# 中序遍历递归实现
def inorderTraversal_recursive(root):
    if not root:
        return []
    return inorderTraversal_recursive(root.left) + [root.val] + inorderTraversal_recursive(root.right)

# 后序遍历递归实现
def postorderTraversal_recursive(root):
    if not root:
        return []
    return postorderTraversal_recursive(root.left) + postorderTraversal_recursive(root.right) + [root.val]

三、非递归实现

非递归实现需手动维护一个栈（Stack）来模拟递归调用栈，更适合理解遍历的底层逻辑，同时可避免递归深度过大导致的栈溢出问题。

1. 前序遍历非递归

前序遍历非递归需先将根节点入栈，每次弹出节点并访问，再将其右子节点和左子节点依次入栈（确保左子树优先访问）。

python
def preorderTraversal_iterative(root):
    if not root:
        return []
    stack, result = [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. 中序遍历非递归

中序遍历需优先遍历到最左侧叶子节点，再依次回溯访问根节点和右子树。

python
def inorderTraversal_iterative(root):
    if not root:
        return []
    stack, result = [], []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

3. 后序遍历非递归

后序遍历非递归实现较为复杂，可采用两个栈：第一个栈存储节点，第二个栈存储后序遍历结果，最终反转第二个栈得到顺序结果。

python
def postorderTraversal_iterative(root):
    if not root:
        return []
    stack1, stack2 = [root], []
    while stack1:
        node = stack1.pop()
        stack2.append(node.val)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    return stack2[::-1]

四、性能分析

遍历方式	时间复杂度	空间复杂度（递归）	空间复杂度（非递归）
前序遍历	O(n)	O(h)（h为树高）	O(n)
中序遍历	O(n)	O(h)	O(n)
后序遍历	O(n)	O(h)	O(n)

时间复杂度：所有遍历方式均需访问每个节点一次，时间复杂度为O(n)，n为节点数。
空间复杂度：递归实现受树高影响（最坏情况为O(n)，平衡树为O(log n)），非递归实现依赖栈，最坏情况下栈中需存储所有节点，为O(n)。

五、总结

递归实现：代码简洁，适合简单场景，但可能存在栈溢出风险。
非递归实现：手动管理栈，灵活性强，适用于复杂场景或对内存控制要求高的场景。
应用场景：根据具体需求选择遍历方式，如中序遍历常用于二叉搜索树的有序输出，后序遍历常用于释放树资源。

通过对比递归与非递归实现，能更深入理解二叉树遍历的本质，同时提升算法设计与代码优化能力。

目录