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

构建二叉树节点类

首先，我们需要定义一个简单的二叉树节点类。每个节点包含值（val）、左子节点（left）和右子节点（right）。

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

递归实现先序遍历

这是最直观、最容易理解的方法。利用函数自身的调用栈来完成遍历过程。

def preorder_traversal_recursive(root):    """    递归实现先序遍历    :param root: TreeNode，二叉树的根节点    :return: List[int]，遍历结果列表    """    result = []        def dfs(node):        if not node:            return        result.append(node.val)   # 访问根节点        dfs(node.left)            # 遍历左子树        dfs(node.right)           # 遍历右子树        dfs(root)    return result

迭代实现先序遍历（使用栈）

除了递归，我们也可以用显式栈来模拟递归过程，这在某些限制递归深度的场景中非常有用。

def preorder_traversal_iterative(root):    """    迭代实现先序遍历    :param root: TreeNode，二叉树的根节点    :return: List[int]，遍历结果列表    """    if not root:        return []        stack = [root]    result = []        while stack:        node = stack.pop()        result.append(node.val)        # 注意：先压入右子节点，再压入左子节点        # 因为栈是后进先出（LIFO）        if node.right:            stack.append(node.right)        if node.left:            stack.append(node.left)        return result

完整示例与测试

下面是一个完整的测试例子，帮助你验证两种方法是否正确：

# 构建如下二叉树：#       1#      / \#     2   3#    / \#   4   5root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)print("递归结果：", preorder_traversal_recursive(root))# 输出：[1, 2, 4, 5, 3]print("迭代结果：", preorder_traversal_iterative(root))# 输出：[1, 2, 4, 5, 3]

总结

通过本教程，你已经掌握了递归实现先序遍历和迭代两种方式。先序遍历在实际开发中常用于复制树结构、序列化二叉树等场景。希望这篇数据结构教程能为你打下坚实基础！

记住，理解遍历的核心思想比死记代码更重要。动手写一写、画一画，你会对Python先序遍历有更深刻的认识。