Python 数据结构与算法 · 二叉树与递归体系总结

基础定义

递归 是一种通过函数调用自身来解决问题的编程方法。它把一个大型复杂的问题层层转化为一个与原问题相似的、规模更小的问题来求解。

递归必须满足两个核心要素：

1.终止条件（Base Case）：问题足够小，可以直接给出答案，不再继续调用自身。2.递推关系（Recursive Relation）：将原问题拆解为子问题，并通过调用自身来解决子问题。

代码实现（以二叉树最大深度为例）

def maxDepth(root):    if root is None:          # ① 终止条件：空树的高度为 0        return 0    left_depth = maxDepth(root.left)   # ② 递：求左子树高度    right_depth = maxDepth(root.right) # ③ 递：求右子树高度（等②返回后才执行）    return max(left_depth, right_depth) + 1  # ④ 归：汇总结果

为什么要这样实现？（执行时序）

递归函数中：

•调用自身之前的代码（如 left_depth = ...）在 “递（压栈）” 阶段执行。•调用自身之后的代码（如 return max(...) + 1）在 “归（出栈）” 阶段执行。

因为“当前节点的高度”依赖于“左右子树的高度”，所以必须先完成子问题的计算（递到底），才能汇总结果（归回来）。这决定了汇总代码必须放在所有递归调用之后。

引申

•递归的优点是代码简洁、逻辑清晰，与数学归纳法思维一致。•缺点在于系统调用栈空间有限，深度过大（如几万层）会导致栈溢出（RecursionError）。此时需要用迭代 + 手动栈替代。

第二部分：二叉树（Binary Tree）

基础定义

二叉树（Binary Tree） 是每个节点最多有两个子树的树结构。每个节点包含三个部分：

•数据域（val）•指向左子树的指针（left）•指向右子树的指针（right）

特殊的二叉树：

•满二叉树：每个节点要么是叶子，要么左右子树都存在。•完全二叉树：除最后一层外，每层节点都填满，且最后一层的节点靠左排列。•二叉搜索树（BST）：左子树所有节点 < 根节点 < 右子树所有节点。

代码实现（二叉树节点定义）

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

第三部分：二叉树的遍历（Traversal）

基础定义

遍历 是按照某种顺序访问树中每一个节点且每个节点只访问一次的过程。二叉树遍历分为两大类：

深度优先搜索（DFS）：沿着一条路径走到底，再回溯。包含三种顺序：

•前序遍历：根 → 左 → 右•中序遍历：左 → 根 → 右•后序遍历：左 → 右 → 根

代码实现（递归版）

def preorder(root):   # 前序    if not root: return []    return [root.val] + preorder(root.left) + preorder(root.right)def inorder(root):    # 中序    if not root: return []    return inorder(root.left) + [root.val] + inorder(root.right)def postorder(root):  # 后序    if not root: return []    return postorder(root.left) + postorder(root.right) + [root.val]

为什么要区分三种顺序？（设计理由）

三种顺序的本质区别是 根节点的访问时机：

•前序（根先访问）：适用于需要“先创建父节点，再创建子节点”的场景。比如 React 的递归渲染，必须先把父 DOM 创建好，才能往里挂子组件。•中序（根在中间）：对于 BST，中序遍历结果必然升序。因此验证 BST 或按顺序输出 BST 数据时，中序是自然选择。•后序（根最后访问）：适用于需要“先处理子节点，再处理父节点”的场景。比如计算树的高度（必须先知道子树的高度），或者删除一个文件夹（必须先把子文件和子文件夹删干净，才能删除自己）。

引申

•三种顺序的递归代码，只有 res.append(root.val) 这一行的位置不同，其余结构完全一致。•如果要求非递归（迭代）实现，需要手动维护栈来模拟系统调用栈，中序和后序的迭代写法比前序更复杂，因为要处理“什么时候弹出并记录”的问题。

第四部分：二叉搜索树（BST）

基础定义

二叉搜索树（BST） 是一种特殊的二叉树，满足：

•左子树上所有节点的值 都小于 根节点的值。•右子树上所有节点的值 都大于 根节点的值。•左右子树也各自是 BST。

核心性质

对 BST 进行中序遍历，得到的结果一定是严格升序的。 这是验证 BST 的最便捷方法。

代码实现（验证 BST，LeetCode 98）

def isValidBST(root):    prev = float('-inf')    def inorder(node):        nonlocal prev        if not node: return True        if not inorder(node.left): return False        if node.val <= prev: return False        prev = node.val        return inorder(node.right)    return inorder(root)

为什么要这样实现？

•利用中序遍历的升序特性，只需记录上一个访问的节点值（prev），检查当前值是否严格大于它。•不需要把整棵树转成数组再检查，节省空间（O(1) 额外空间，不算递归栈）。

引申

•BST 的查找、插入、删除平均时间复杂度为 O(log n)，前提是树保持平衡。•如果插入顺序特殊（如升序插入），BST 会退化成链表，性能降为 O(n)。因此工程中常用 平衡二叉树（AVL） 或 红黑树。

第五部分：二叉树直径（Diameter of Binary Tree，LeetCode 543）

基础定义

二叉树的直径 是指树中任意两个节点之间最长路径上的边数。

•这条路径不一定经过根节点。•路径长度按 边数 计算（一个节点到其子节点为 1 条边）。

代码实现

def diameterOfBinaryTree(root):    diameter = 0    def depth(node):        nonlocal diameter        if not node:            return 0        left = depth(node.left)        right = depth(node.right)        # 经过当前节点的最长路径 = left + right（边数）        diameter = max(diameter, left + right)        # 向上返回当前节点的高度（边数）        return max(left, right) + 1    depth(root)    return diameter

为什么要这样实现？（设计理由拆解）

1.为什么需要两个“出口”？

•向上返回（return max(left, right) + 1）：父节点需要知道“我这棵子树有多高”，才能计算经过父节点的路径。这是唯一能向上传递的信息。•全局更新（diameter = max(...)）：直径是“经过当前节点的最长路径”，即 left + right。但这个值对父节点没有用（父节点只需要高度，不能把左右两边都拿上来），所以不能作为返回值，只能作为“副作用”记录在外部变量中。

2.为什么 left + right 能代表“经过当前节点的最长路径”？
经过当前节点的路径，必须从左子树的最深节点上来，穿过当前节点，再到右子树的最深节点。边数就是“左子树高度” + “右子树高度”。

3.为什么不能直接计算 maxDepth(root.left) + maxDepth(root.right)？
因为直径可能不经过根节点。如果子树内部有一条更长的路径（比如左子树内部的路径长度就大于经过根的任何路径），则必须遍历每个节点，在每个节点处都尝试更新直径。

引申

•这道题是后序遍历 + 全局变量的标准模板，与 LCA（最近公共祖先）共享同一套递归骨架。•如果题目改成“路径上的节点数”，只需把 left + right 改为 left + right + 1 即可。

第六部分：手动栈模拟递归（Iteration with Explicit Stack）

基础定义

手动栈模拟 是指用程序员自己维护的栈数据结构，代替系统调用栈，来实现递归算法的迭代版本。

•目的：避免递归深度过大导致栈溢出。•代价：代码更复杂，需要额外维护状态（state 标记）和中间结果（如 height 字典）。

代码实现（以二叉树直径为例）

def diameterOfBinaryTree(root):    if not root: return 0    stack = [(root, 0)]  # 0 = 未处理子树，1 = 子树已处理    height = {None: 0}    diameter = 0    while stack:        node, state = stack.pop()        if state == 0:            # 递：压入当前节点（标记为待计算），再压入右、左子树            stack.append((node, 1))            if node.right:                stack.append((node.right, 0))            if node.left:                stack.append((node.left, 0))        else:            # 归：左右子树高度已经算好，存于 height 字典            left_h = height.get(node.left, 0)            right_h = height.get(node.right, 0)            diameter = max(diameter, left_h + right_h)            height[node] = max(left_h, right_h) + 1    return diameter

为什么要这样实现？

•state 标记：递归中，系统栈帧记录了“我执行到哪一行了”。迭代中必须显式标记一个节点是“刚进来，还没处理子树”（state=0），还是“子树已处理完，该计算我了”（state=1）。•压栈顺序：栈是 LIFO（后进先出）。为了先处理左子树，再处理右子树，必须 先压右，再压左，这样弹出时左子树先被处理。•height 字典：递归中，子节点的高度存在栈帧的局部变量里（如 left_depth）。迭代中需要一个“外挂内存”来存储每个节点的高度，以便父节点在 state=1 时取出来用。

引申

•手动栈能有效避免递归深度限制，适合处理深度不确定的树。•但在工程中，除非确定递归会爆栈，否则优先使用递归，因为它更接近人类思维，维护成本低。

第七部分：回溯（Backtracking）

基础定义

回溯 是一种通过尝试所有可能的候选解来找出所有解的算法思想。它通常使用递归实现，其核心特征是：

•在“递”的阶段做出一个选择（修改状态）。•递归深入，探索该选择下的所有可能性。•在“归”的阶段撤销该选择（恢复状态），以便尝试下一个候选。

回溯 = 暴力枚举 + 剪枝（可选）。

代码实现（全排列，LeetCode 46）

def permute(nums):    res, path = [], []    used = [False] * len(nums)    def backtrack():        if len(path) == len(nums):            res.append(path[:])  # 拷贝，防止后续修改污染            return        for i in range(len(nums)):            if used[i]:                continue            # ① 递：做选择            path.append(nums[i])            used[i] = True            # ② 深入            backtrack()            # ③ 归：撤销选择            used[i] = False            path.pop()    backtrack()    return res

为什么要这样实现？

1. 为什么“做选择”和“撤销选择”必须成对出现？
因为 path 和 used 是全局共享的状态。如果当前分支探索完后不恢复，下一个分支会看到被污染的状态，导致结果重复或遗漏。撤销选择是回溯的“灵魂”。

引申

•回溯适用于组合、排列、子集、N 皇后、数独等所有搜索类问题。•剪枝 是在“递”的入口处，提前判断当前路径已经不可能得到有效解，直接 return，避免无谓的深入。•正则表达式引擎的 NFA 匹配，本质就是回溯，可能引发“灾难性回溯”（Catastrophic Backtracking）。

第八部分：工程能力引申（GitHub / 开源项目映射）

第九部分：总结与进阶路线图

你现在已经具备以下核心能力：

•✅ 能精准分析递归函数的“递”与“归”执行时序•✅ 熟练掌握二叉树的前、中、后、层四种遍历，并理解其工程映射•✅ 能独立推导翻转、合并、BST 验证、LCA、直径等经典题目的代码设计逻辑•✅ 理解递归与迭代（手动栈）的互换本质，知道迭代要额外维护状态和中间结果•✅ 掌握回溯的“做选择 → 递归 → 撤销选择”通用模板，理解状态恢复的必要性