Python递归实现二叉树遍历

最近在刷LeetCode时，递归我遇到了个挺有意思的实现问题：怎么用递归实现二叉树的三种遍历方式？当时对着屏幕发呆了半小时，突然想起邻居家小孩搭积木的叉树场景——其实二叉树就像立体积木，遍历就是遍历找到每个木块的查看顺序嘛！今天我们就用这个生活化的递归比喻，手把手实现Python版的实现遍历算法。

先搭个积木架：构建二叉树节点

就像搭积木需要基础模块，叉树我们先定义树的遍历节点。在Python里用类来实现特别合适：

class TreeNode:def __init__(self,递归 value):self.val = valueself.left = Noneself.right = None

假设我们要构建下面这棵积木树：

动手搭树

• 根节点A= TreeNode('A')
• 左孩子B：A.left = TreeNode('B')
• 右孩子C：A.right = TreeNode('C')

前序遍历：先看房顶再看墙

就像进房间先看吊灯（根节点），再看左边墙上的遍历画（左子树），最后看右边书架（右子树）。递归这个顺序用递归实现特别优雅：

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

运行这个函数会返回类似['A',实现'B','D','E','C']的结果。注意递归终止条件：当遇到空节点（None）时返回空列表。叉树

递归过程拆解

• 第1步：访问A，记录A
• 第2步：向左探索B，记录B
• 第3步：继续向左到底，记录D
• 第4步：向右看E，记录E
• 最后处理C

中序遍历：从地基开始观察

这种遍历就像先检查左边地基（左子树），再看主梁（根节点），最后检查右边结构（右子树）。调整递归顺序就能实现：

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

对于我们的示例树，输出会是['D','B','E','A','C']。特别注意当处理到叶子节点时，左右子树都是空列表。

递归栈模拟

后序遍历：最后检查承重墙

这种遍历方式就像装修师傅最后检查承重结构：先看左边结构，再看右边结构，最后确认主梁。代码稍微调整下拼接顺序：

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

运行结果会是['D','E','B','C','A']。这时候根节点永远在最后出现，适合某些特定场景比如计算目录大小。

递归的魔法与陷阱

虽然递归代码很简洁，但要注意Python的默认递归深度限制（约1000层）。就像搭积木太高会倒，处理超深二叉树时可能会遇到栈溢出。这时候就得改用迭代写法了。

试着用这几种方法遍历你自己构建的二叉树吧！当看到输出结果符合预期时，那种成就感就像第一次成功搭起乐高城堡。下次如果遇到非递归实现的题目，你会发现这些递归经验就像预先准备好的积木块，能快速组合出新解法。

参考文献：《算法导论》第三版中树遍历的相关章节，LeetCode题库的二叉树经典题目。窗外的麻雀又在电线杆上多嘴，这个夏天，用代码和二叉树谈场不分手的恋爱如何？