二叉树：二叉树的三种遍历方式，递归实现超简单

二叉树是一种非常基础的数据结构，每个节点最多有两个子节点（左子树和右子树）。遍历二叉树就是按照特定顺序访问每个节点，就像逛超市时按顺序逛货架一样。今天我们要学的是二叉树最经典的三种遍历方式：前序、中序、后序，而且用递归实现，简单易懂！

先搞懂：什么是递归？¶

递归就像“套娃”——函数自己调用自己，但每次处理的“范围”更小，直到遇到终止条件（比如“套”到空盒子就停止）。举个例子：你要计算1+2+3+…+n，递归的思路是先算1+2+…+(n-1)，再加上n。

二叉树的三种遍历顺序¶

遍历顺序的关键是“根节点”的访问位置，三种方式分别是：
- 前序遍历：根 → 左子树 → 右子树（先看根，再逛左货架，最后逛右货架）
- 中序遍历：左子树 → 根 → 右子树（先逛左货架，再看根，最后逛右货架）
- 后序遍历：左子树 → 右子树 → 根（先逛左、右货架，最后看根）

用例子理解遍历过程¶

我们用一个具体的二叉树举例，方便直观感受：

    1
   / \
  2   3
 / \
4   5

这个树的结构是：根节点是1，左子树的根是2，右子树的根是3；2的左孩子是4，右孩子是5。

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

顺序：先访问根节点，再遍历左子树，最后遍历右子树。

递归实现：¶

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

def preorder(root):
    if root is None:  # 终止条件：空节点直接返回
        return
    print(root.val, end=" ")  # 访问根节点
    preorder(root.left)       # 递归左子树
    preorder(root.right)      # 递归右子树

遍历过程（以上面的树为例）：¶

• 从根节点1开始，打印1 → 进入左子树（节点2）
• 打印2 → 进入左子树（节点4）
• 节点4没有子节点，打印4 → 返回上一层
• 回到节点2，进入右子树（节点5），打印5 → 返回上一层
• 回到根节点1，进入右子树（节点3），打印3 → 结束

遍历结果：1 2 4 5 3

2. 中序遍历（左根右）¶

顺序：先遍历左子树，再访问根节点，最后遍历右子树。

递归实现：¶

def inorder(root):
    if root is None:
        return
    inorder(root.left)        # 递归左子树
    print(root.val, end=" ")  # 访问根节点
    inorder(root.right)       # 递归右子树

遍历过程：¶

• 递归到左子树最深处（节点4），打印4 → 返回
• 回到节点2，打印2 → 进入右子树（节点5），打印5 → 返回
• 回到根节点1，打印1 → 进入右子树（节点3），打印3 → 结束

遍历结果：4 2 5 1 3

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

顺序：先遍历左子树，再遍历右子树，最后访问根节点。

递归实现：¶

def postorder(root):
    if root is None:
        return
    postorder(root.left)      # 递归左子树
    postorder(root.right)     # 递归右子树
    print(root.val, end=" ")  # 访问根节点

遍历过程：¶

• 递归到左子树最深处（节点4），打印4 → 返回
• 递归到节点5，打印5 → 返回
• 回到节点2，打印2 → 递归右子树（节点3），打印3 → 返回
• 回到根节点1，打印1 → 结束

遍历结果：4 5 2 3 1

三种遍历的核心区别¶

递归的关键思想¶

1. 终止条件：当当前节点为空（root is None）时，直接返回，不再递归。
2. 递归逻辑：根据遍历顺序，先处理当前节点（根），再递归左右子树（顺序不同，处理顺序不同）。
3. “自顶向下”的执行：从根节点开始，逐步深入到叶子节点，再回溯处理上层节点。

通过递归实现三种遍历，你会发现核心是“明确顺序，递归调用”。只要记住每种遍历的“根位置”，就能轻松写出递归函数。多动手画一画树的结构，跟着递归过程走一遍，很快就能掌握啦！