深入理解Python中序遍历（手把手教你实现二叉树中序遍历算法）

为什么学习中序遍历？

掌握Python数据结构中的树结构及其遍历方法，不仅能帮助你解决面试题，还能提升你对递归遍历算法的理解能力。中序遍历在表达式求值、BST验证、排序等场景中都有广泛应用。

准备工作：定义二叉树节点

首先，我们需要定义一个简单的二叉树节点类：

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

方法一：递归实现中序遍历

递归是最直观、最容易理解的实现方式。我们按照“左→根→右”的顺序编写函数：

def inorderTraversal(root):    result = []        def inorder(node):        if node is not None:            inorder(node.left)      # 遍历左子树            result.append(node.val) # 访问根节点            inorder(node.right)     # 遍历右子树        inorder(root)    return result  

使用示例：

# 构建如下二叉树：#       1#        \#         2#        /#       3root = TreeNode(1)root.right = TreeNode(2)root.right.left = TreeNode(3)print(inorderTraversal(root))  # 输出: [1, 3, 2]  

方法二：迭代实现中序遍历（使用栈）

虽然递归简洁，但在处理极深的树时可能引发栈溢出。因此，我们也可以用显式栈来模拟递归过程：

def inorderTraversalIterative(root):    result = []    stack = []    current = root        while stack or current:        # 一直向左走到底，并将路径上的节点入栈        while current:            stack.append(current)            current = current.left                # 弹出栈顶（即最左节点）        current = stack.pop()        result.append(current.val)                # 转向右子树        current = current.right        return result  

总结

通过本教程，你已经掌握了Python中序遍历的两种核心实现方式：递归与迭代。无论是为了面试准备，还是深入理解Python数据结构，这些知识都将为你打下坚实基础。

记住，中序遍历的关键在于“左→根→右”的访问顺序。多加练习，你就能熟练运用这一经典递归遍历算法，轻松应对各种与二叉树中序遍历相关的问题！