Python二叉树深度优先遍历：递归与迭代写法及实战应用

用递归去写树结构，代码往往只有几行，但真正想追每一步执行时，思维很容易打结。这篇文章属于 Python 算法系列的二叉树专题，核心聊的是深度优先遍历算法（DFS）的递归与迭代写法，以及它在实际问题里到底怎么用。适合三类人看：刚接触数据结构的学生、准备算法面试的朋友，以及在项目里被树形数据折腾过的后台开发。读完你能拿到一套能直接跑的遍历模板，还能避开一些只有真正跑过代码才会遇到的问题。

1. 树的遍历从什么开始：一棵二叉树的代码长相

1.1 用类把二叉树“造”出来

在 Python 里定义一棵二叉树，最常见的做法就是写一个节点类。每个节点只关心三件事：自己的值、左孩子、右孩子。孩子为空就用None表示，整棵树就是一层套一层的引用关系。

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

这段类代码几乎是所有树题答案的前三行。别看它简单，里面藏着两个容易忽略的细节。

第一，val默认给0，是为了创建节点时只传一个值也能正常工作。第二，left和right默认是None，意味着只传val时，构造出来的就是一个叶子节点。这两个默认值写在这里，不是拍脑袋决定的，而是为了保证“空子树”有明确的表示方式，后面的递归出口全靠它。

造一棵具体的树也很直接：

root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5)

这棵树长这样：

1 / \ 2 3 / \ 4 5

很多人在构造这一步没什么问题，问题出在“遍历”的时候。脑子里容易把树想成一串平铺的节点，却忽略了树的递归定义：一棵二叉树，要么是空树，要么是一个根节点加上左右两棵子树。这个递归定义直接决定了 DFS 的代码形状，也决定了为什么遍历算法的核心逻辑可以短到几行。

1.2 三种访问顺序的差异

深度优先遍历到了某个节点，总要面对三个动作：处理当前节点、深入左子树、深入右子树。三个动作排列组合一下，常见的只有三种：

这三种顺序的差异，核心就是“当前节点的处理动作放在哪个位置”。放最前面就是前序，放中间就是中序，放最后就是后序。代码层面它们几乎一样，差别只是几行代码的顺序。可顺序不同，解决的实际问题完全不同。

举个例子，如果一棵树表示数学表达式，前序遍历得到的是前缀表达式，中序遍历得到的近似中缀表达式，后序遍历得到的是后缀表达式。同一棵树，只是改变访问顺序，输出含义就变了。这也是为什么很多算法题表面在考遍历，实际考的是“你知不知道在哪个时机处理节点”。

2. 递归版深度优先遍历：顺着函数调用理解前中后序

递归版 DFS 与其说是一个“算法”，不如说是在利用函数调用栈。你不需要手动维护栈，Python 会替你完成。理解递归版的关键，是明白每次函数调用钻进左子树或右子树时，当前函数并没有结束，它还在栈上等着，等左右子树全部返回后，才会继续执行后面的代码。

2.1 递归停止条件：None 节点是出口

写任何树的递归代码，第一步都是问自己：这个函数什么时候结束？二叉树的递归出口就是遇到空节点时返回。这一步虽然只有一行，但漏掉的话，程序通常不会立刻报错，而是会一直往下一层访问不存在的节点，直到触发AttributeError或者RecursionError。

这里的None节点就是整个递归的“刹车”。代码里常常这么写：

def dfs(node): if node is None: return # 在这里可以处理当前节点 dfs(node.left) # 也可以在这里处理当前节点 dfs(node.right) # 还可以在这里处理当前节点

if node is None: return是函数的统一出口。只要节点为空，就表示这棵子树不存在，没有必要继续递归。理解了这个出口，后面三种遍历的实现就只是“把处理当前节点的语句放到不同位置”而已。

2.2 先序遍历：先处理当前节点

先序遍历的顺序是中、左、右。代码框架非常简单：

def preorder_recursive(root): result = [] def traverse(node): if node is None: return result.append(node.val) traverse(node.left) traverse(node.right) traverse(root) return result

用前面的树跑一遍，结果会是[1, 2, 4, 5, 3]。执行过程可以这样理解：进入节点 1，立刻把 1 记录下来，然后去左边；进入节点 2，立刻记录 2，然后去左边；进入节点 4，记录 4，左右为空，返回；回到节点 2，继续去右边；进入节点 5，记录 5，返回；回到节点 1，继续去右边。

这里有个很多人问过的点：为什么traverse是嵌套函数，却不需要nonlocal result？因为result.append(...)是在原地修改列表对象，并没有给result重新赋值。如果你写成result = result + [node.val]，那确实需要nonlocal result。这个细节很细微，但在面试中很容易被追问。

2.3 中序和后序：挪一行代码，用途完全不同

中序遍历只需要把result.append放到两个递归调用之间：

def inorder_recursive(root): result = [] def traverse(node): if node is None: return traverse(node.left) result.append(node.val) traverse(node.right) traverse(root) return result

输出是[4, 2, 5, 1, 3]。中序遍历在二叉搜索树里格外重要，因为一棵二叉搜索树的中序序列一定是递增的。判断一棵树是不是二叉搜索树，最常见的思路就是跑一次中序遍历，检查结果是否严格递增。

后序遍历则是把处理语句放到最后：

def postorder_recursive(root): result = [] def traverse(node): if node is None: return traverse(node.left) traverse(node.right) result.append(node.val) traverse(root) return result

输出是[4, 5, 2, 3, 1]。后序的顺序意味着“先处理子树，再处理当前节点”，它特别适合自底向上的场景。比如统计一棵树有多少个节点：

def count_nodes(root): if root is None: return 0 return count_nodes(root.left) + count_nodes(root.right) + 1

这个函数先数左子树，再数右子树，最后加上自己。它的处理顺序就是后序。很多看起来和遍历无关的树形问题，底层都藏着这个结构。

3. 迭代版 DFS：把递归栈搬到明面上

递归代码很直观，但它不是万能的。首先，Python 默认递归层数只有 1000 左右，树一旦特别深，直接报RecursionError。其次，每次函数调用都有额外开销，在性能敏感的场景里，递归版本可能不是最优选择。更重要的是，迭代版本能让你真正体会到 DFS 的本质：后进先出，也就是栈。

3.1 前序遍历的迭代写法

前序遍历的顺序是中、左、右。既然要用栈模拟，就要想清楚“先压谁，后压谁”。因为栈是后进先出，所以希望先访问左子树，就得让左子树最后压进栈。换句话说是先压右孩子，再压左孩子。

def preorder_iterative(root): if root is None: return [] stack = [root] result = [] while stack: node = stack.pop() result.append(node.val) if node.right is not None: stack.append(node.right) if node.left is not None: stack.append(node.left) return result

第一次执行时，可以自己拿笔走一遍：先把根节点 1 弹出，记录 1；然后压入右孩子 3，再压入左孩子 2；下一次弹出的是 2，记录 2；接着压入 2 的右孩子 5，压入左孩子 4；弹出 4，记录；弹出 5，记录；弹出 3。最终结果和递归版完全一致。

这个版本有个好处：它不需要判断node是否为空，而是提前在入栈时检查None。两种防御方式都是对的，选择哪一种取决于你更习惯哪种代码风格。

3.2 中序遍历的迭代写法：一路压左，再回头

中序遍历就没有前序那么好写了，因为访问当前节点的时机，是左子树全部处理完之后。迭代时要模拟一个行为：沿着左子树一路往下压栈，直到空，然后弹出并访问，再转向右子树。

def inorder_iterative(root): stack = [] cur = root result = [] while cur is not None or stack: while cur is not None: stack.append(cur) cur = cur.left cur = stack.pop() result.append(cur.val) cur = cur.right return result

这个版本的边界条件while cur is not None or stack很容易写错。如果只写while stack，初始时栈为空，树不为空，循环根本进不去。如果只写while cur is not None，那弹出节点后转向右子树时，右子树为空就结束了，但栈里可能还剩下没处理的节点。

我每次写这个模板，都会在脑子里默念一句话：先走到最左下角，走不动了，弹一个，往右走一步，再继续往左下钻。掌握了这句话，中序遍历的迭代版就不会再丢边界条件。

3.3 后序遍历的迭代写法：双栈法和标记法

后序遍历的迭代版本是三种里面最容易绕晕的。这里分享一个取巧思路：前序遍历是“中、左、右”，如果改成“中、右、左”，再把结果反转，就得到了“左、右、中”，也就是后序遍历。

def postorder_iterative(root): if root is None: return [] stack = [root] reverse_result = [] while stack: node = stack.pop() reverse_result.append(node.val) if node.left is not None: stack.append(node.left) if node.right is not None: stack.append(node.right) return reverse_result[::-1]

注意这里和前序迭代版本的差异：前序是先压右再压左，这里恰恰相反，是先压左再压右。原因很简单，前序要“中左右”，所以要弹出左子树后马上处理；这里要“中右左”，所以要把右子树留在上面，因此先压左，后压右自然会先弹出右。

如果你不希望反转结果，也可以用“记录上一次访问节点”的标记法：

def postorder_iterative_mark(root): stack = [] cur = root prev = None result = [] while stack or cur: while cur is not None: stack.append(cur) cur = cur.left node = stack[-1] if node.right is not None and node.right != prev: cur = node.right else: result.append(node.val) prev = stack.pop() return result

这个代码的核心是：只有当右子树为空，或者右子树已经被访问过，才能访问当前节点。否则要先处理右子树。标记法虽然代码稍长，但它体现的“回溯”思想在后续做路径类问题时很有帮助。

4. 深度优先搜索能直接搞定的二叉树实战题

遍历模板背熟之后，真正的价值是拿它们去解决实际问题。这一节是我觉得最值得反复看的部分，因为很多题目看起来包装得很复杂，本质还是 DFS。

4.1 求二叉树最大深度

最大深度的定义是从根节点到最远叶子节点的最长路径上的节点数。这个问题用递归写非常自然：

def max_depth(root): if root is None: return 0 left_depth = max_depth(root.left) right_depth = max_depth(root.right) return max(left_depth, right_depth) + 1

理解这个代码的关键是把它当成后序遍历：先分别求出左子树和右子树的最大深度，然后取较大值，再加上当前节点这一层。递归的运行过程是从上往下调用，但结果是从下往上返回的。这一步理解了，很多“自底向上”的树形问题就都通了。

迭代写法也可以做，比如在层序遍历时记录层数，或者用带值栈模拟。不过求深度这个场景，递归版本是表达力最好的，所以优先推荐。

4.2 判断路径和是否等于目标值

给定一棵二叉树和一个目标值，判断是否存在从根节点到叶子节点的路径，使得路径上所有节点值相加等于目标值。题目看着复杂，其实只需要带着“还需要多少”这个信息不断向下搜索。

def has_path_sum(root, target_sum): if root is None: return False if root.left is None and root.right is None: return root.val == target_sum return has_path_sum(root.left, target_sum - root.val) or has_path_sum(root.right, target_sum - root.val)

这个代码值得细品。每次进入子节点之前，把目标值减去当前节点的值，这样问题就转化成了“子树里是否存在一条路径，使得剩余目标值成立”。递归的返回值是一个布尔值，两个子问题用or连接，只要其中一个为True，整条路径就存在。

我见过不少人一开始会写一个current_sum累加版本，也能做出来，但减法版本更简洁，也更符合“问题规模不断缩小”的递归思路。

4.3 序列化与反序列化：把二叉树存进字符串

序列化的目标是把一棵二叉树变成字符串，反序列化再把字符串还原成原来的树。最常见的方法是前序遍历，遇到空节点用特殊字符#表示。

def serialize(root): parts = [] def helper(node): if node is None: parts.append("#") return parts.append(str(node.val)) helper(node.left) helper(node.right) helper(root) return ",".join(parts)

反序列化时需要按顺序读取字符串，遇到#就返回None，否则创建节点，并继续用递归构建左右子树：

def deserialize(data): values = data.split(",") index = 0 def helper(): nonlocal index if values[index] == "#": index += 1 return None node = TreeNode(int(values[index])) index += 1 node.left = helper() node.right = helper() return helper()

这里有个非直观的点：反序列化函数的推进顺序和前序遍历完全一致，所以可以用同一个helper在进入左子树后自然接着构建右子树。只要严格按照“先根，再左，再右”的顺序读取，字符串里每一个值都能被正确消费掉。

这种写法的实用价值很大。缓存、存储、网络传输树结构时，字符串是一个极其朴素的中间格式。配合前序遍历模板，哪怕不能使用内置序列化工具，你也能手写一套。

4.4 判断二叉树是否对称

对称树的判断，可以看成是“两棵子树同时做镜像 DFS”。判断条件也顺理成章：左右两个节点的值相等，且左节点的左子树与右节点的右子树对称，左节点的右子树与右节点的左子树对称。

def is_symmetric(root): if root is None: return True def check(left, right): if left is None and right is None: return True if left is None or right is None: return False return (left.val == right.val and check(left.left, right.right) and check(left.right, right.left)) return check(root.left, root.right)

这个题很适合练“抽象的 DFS”：不是在一棵树上往深处走，而是同时在两棵树上按相反方向走。它锻炼的正是遍历顺序的变体意识。如果三种基础遍历你只是背会了模板，遇到这种题还是会卡壳，但如果你理解了“处理动作放在哪个位置决定了遍历含义”，这个题目其实一眼就能看穿。

5. 我踩过的坑：递归深度、空指针与共享变量

算法模板好看，但实战代码总会遇到一些模板之外的问题。只能说，这些坑都是我实际跑代码时踩过的，写下来给大家省点时间。

5.1 递归默认深度只有 1000 层

Python 为了防止栈溢出，设置了递归深度限制，通常默认是 1000。二叉树如果退化成链表形状，比如每个节点都只有右孩子，递归深度就约等于节点数量。节点一多，程序直接报RecursionError。

有人会第一时间想到调高限制：

import sys sys.setrecursionlimit(100000)

这个做法在本地调试时可以应急，但不是所有环境都允许你随便改。更深层的问题是：递归版 DFS 的空间复杂度本身是 O(h)，h 是树高，极端情况下等于 O(n)。与其无脑调高递归限制，不如先评估这棵树可能有多深。如果深度确实可能极大，就老老实实换成迭代版的栈写法，这才是一劳永逸的方案。

实际工作中我遇到过的一个场景是解析某些嵌套配置结构，层级很深，递归版一跑就挂。换上迭代版之后，问题立刻消失。所以说，递归迭代两种版本并不是考试工具，而是两套都必须掌握的“手动挡”和“自动挡”。

5.2 可变对象作为默认参数的风险

Python 里最常见的坑之一，就是把可变对象放到函数默认参数里。写树遍历时，有人会图省事这样写：

# 需要避免的写法 def preorder(root, result=[]): if root is None: return result result.append(root.val) preorder(root.left, result) preorder(root.right, result) return result

第一次调用没问题，第二次调用同一个函数时，result会保留上一次的数据，导致结果累加。原因是 Python 的函数默认参数在定义时只创建一次，之后的每次调用如果不传新值，用的都是同一个列表对象。

安全的写法是把结果列表放在递归函数的外部，或者每次调用都显式传入新列表：

def preorder(root): result = [] def traverse(node): if node is None: return result.append(node.val) traverse(node.left) traverse(node.right) traverse(root) return result

嵌套函数配合闭包变量，既避免了默认参数共享问题，也保持了函数的对外接口整洁。

5.3 返回值和全局变量，选一个就好，别混着用

这是我在做路径求和、最大深度这类题目时最深的体会。一个递归函数，既想通过返回值把结果抛上去，又想通过外部变量把过程记录下来，很容易把自己绕晕。

以“计算从根到叶子的最大路径和”为例，可以用带外部变量的写法：

def max_path_sum(root): best = float("-inf") def dfs(node, current_sum): nonlocal best if node is None: return current_sum += node.val if node.left is None and node.right is None: best = max(best, current_sum) dfs(node.left, current_sum) dfs(node.right, current_sum) dfs(root, 0) return best

也可以用纯递归返回值写法：

def max_path_sum(root): if root is None: return float("-inf") if root.left is None and root.right is None: return root.val return root.val + max(max_path_sum(root.left), max_path_sum(root.right))

两种方式都能得到正确答案，但思路完全不同。第一种是“从上往下累计，到叶子时更新答案”，第二种是“左右子树结果返回后，再与当前值合并”。混着用的时候，最常见的问题就是：递归函数明明该返回子树的合并结果，你却因为外部变量已经记过答案，就在某个分支里忘了处理返回值，结果拿到的值完全不对。

我的建议是，在写之前先问自己一个问题：这个问题适合“自顶向下”还是“自底向上”？如果是自顶向下，就大胆用外部变量传状态；如果是自底向上，就坚持使用返回值。两条路都通的时候，选一条自己最不容易写错的，别来回横跳。

5.4 调试 DFS 的小习惯

最后分享一个我自己的调试习惯：不要只在心里模拟递归，也不要一上来就打印全部调用过程。我通常会用三五个节点构造一棵最小树，然后手动记下“本轮访问的节点、当前栈或递归层、下一步去哪”。前序遍历调错了，大概率是入栈顺序反了；中序遍历调错了，大概率是cur指针和stack的关系没理清；后序遍历调错了，大概率是右子树的处理时机不对。

用这种方法调错，通常几分钟内就能定位到具体是哪一步的顺序问题。比起直接搜答案，这个排查过程对人的训练价值大得多。

深度优先遍历算法在工作中的影子远比想象中多。文件目录的递归遍历、表达式树的计算、配置树的前序遍历转格式，甚至很多搜索引擎的爬取策略，抽象到底层都离不开这套“沿着一条分支走到黑，再回头”的思维方式。把递归版和迭代版都吃透，面试题也好，实际项目也罢，你会发现自己能更快地识别出“这题本质就是个 DFS”。