深入理解二叉树遍历（Python实现详解）

定义二叉树节点

在 Python 中，我们通常使用类来定义二叉树的节点：

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

这个类包含三个属性：节点值 val、左子节点 left 和右子节点 right。

1. 前序遍历（根 → 左 → 右）

前序遍历的顺序是：先访问根节点，再递归地遍历左子树，最后遍历右子树。

递归实现

def preorderTraversal(root):    if not root:        return []    return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)  

迭代实现（使用栈）

def preorderTraversalIterative(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. 中序遍历（左 → 根 → 右）

中序遍历常用于二叉搜索树（BST），因为按此顺序遍历 BST 会得到一个升序序列。

递归实现

def inorderTraversal(root):    if not root:        return []    return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)  

3. 后序遍历（左 → 右 → 根）

后序遍历在删除节点或计算目录大小等场景中非常有用。

递归实现

def postorderTraversal(root):    if not root:        return []    return postorderTraversal(root.left) + postorderTraversal(root.right) + [root.val]  

4. 层序遍历（广度优先遍历）

层序遍历也叫广度优先搜索（BFS），它按层级从上到下、从左到右访问节点。这是唯一一种非递归天然适用的遍历方式，通常使用队列实现。

from collections import dequedef levelOrderTraversal(root):    if not root:        return []    queue = deque([root])    result = []    while queue:        node = queue.popleft()        result.append(node.val)        if node.left:            queue.append(node.left)        if node.right:            queue.append(node.right)    return result  

总结

通过本教程，你已经掌握了 Python二叉树遍历 的四种基本方法。无论是使用递归还是迭代，关键在于理解每种遍历的访问顺序。对于初学者来说，建议先掌握递归写法，再尝试迭代实现以加深对栈和队列的理解。

这些遍历算法不仅是面试高频考点，也是解决更复杂树形问题（如路径查找、树的序列化等）的基础。希望你能动手实践，真正掌握 二叉树深度优先搜索 和 二叉树广度优先遍历 的核心思想！

记住：编程不是看会的，而是练会的。快去 LeetCode 或其他平台找几道题试试吧！