递归 - 二叉树中的深度优先搜索（DFS）

深度优先搜索（DFS）是遍历或搜索树或图数据结构的一种基本算法策略。在二叉树的应用中，DFS通过沿着每条分支尽可能深的探索，直到到达叶子节点，然后回溯继续探索其他分支。递归是实现DFS最自然、最符合直觉的方式，因为它直接反映了树结构的自相似特性。

三种基本遍历方式

1. 前序遍历（Pre-order Traversal）

前序遍历遵循"根-左-右"的访问顺序：

1. 首先访问当前节点（根节点）
2. 然后递归遍历左子树
3. 最后递归遍历右子树

def preorder(root):
    if not root:  # 基准条件：空节点直接返回
        return
    print(root.val)  # 访问根节点（这里可以替换为任何操作）
    preorder(root.left)  # 递归处理左子树
    preorder(root.right)  # 递归处理右子树

应用场景：

• 复制树结构：前序遍历可以在创建父节点后立即创建其子节点
• 前缀表达式计算（波兰表示法）：如表达式树的前序遍历产生前缀表达式
• 序列化二叉树：将树结构转换为字符串表示
• 打印结构化文档的目录（如XML文档）

2. 中序遍历（In-order Traversal）

中序遍历遵循"左-根-右"的访问顺序：

1. 首先递归遍历左子树
2. 然后访问当前节点
3. 最后递归遍历右子树

def inorder(root):
    if not root:  # 基准条件
        return
    inorder(root.left)  # 先处理左子树
    print(root.val)  # 访问根节点
    inorder(root.right)  # 再处理右子树

应用场景：

• 二叉搜索树（BST）中的升序/降序输出：BST的中序遍历会产生有序序列
• 表达式树求值：对于数学表达式树，中序遍历会产生中缀表达式
• 查找BST中的第k小元素
• 验证BST的有效性

3. 后序遍历（Post-order Traversal）

后序遍历遵循"左-右-根"的访问顺序：

1. 首先递归遍历左子树
2. 然后递归遍历右子树
3. 最后访问当前节点

def postorder(root):
    if not root:  # 基准条件
        return
    postorder(root.left)  # 先处理左子树
    postorder(root.right)  # 再处理右子树
    print(root.val)  # 最后访问根节点

应用场景：

• 删除树节点：需要先删除子节点才能安全删除父节点
• 计算表达式树的值：需要先计算子树的值才能计算当前节点的值
• 计算目录大小（需要先计算子目录大小）
• 释放二叉树内存
• 计算树的高度

递归实现DFS的要点

1. 基准条件（Base Case）：

   • 必须明确定义递归终止的条件
   • 对于二叉树通常是当前节点为空（if not root: return）

2. 递归关系（Recursive Relation）：

   • 将问题分解为更小的相同子问题
   • 对于二叉树通常是分解为左子树和右子树的处理

3. 访问时机：

   • 决定是前序、中序还是后序遍历的关键
   • 取决于何时处理当前节点（在其他递归调用之前、之间或之后）

4. 递归调用栈：

   • 每次递归调用都会在调用栈中创建一个新的栈帧
   • 栈深度等于当前路径的深度

典型问题示例

1. 计算二叉树的最大深度

def maxDepth(root):
    if not root:  # 空树的深度为0
        return 0
    left_depth = maxDepth(root.left)  # 计算左子树深度
    right_depth = maxDepth(root.right)  # 计算右子树深度
    return max(left_depth, right_depth) + 1  # 当前节点深度为较大子树深度+1

时间复杂度：O(n)，需要访问每个节点一次 空间复杂度：O(h)，h为树的高度，代表递归调用栈的深度

2. 判断二叉树是否对称

def isSymmetric(root):
    def helper(left, right):
        if not left and not right:  # 两个都为空，对称
            return True
        if not left or not right:  # 只有一个为空，不对称
            return False
        # 当前节点值相等，且左的左与右的右对称，左的右与右的左对称
        return (left.val == right.val and 
                helper(left.left, right.right) and 
                helper(left.right, right.left))
    
    return helper(root, root) if root else True  # 空树视为对称

算法思路：

• 将问题转化为判断两棵树是否是彼此的镜像
• 递归比较左子树的左子树与右子树的右子树
• 比较左子树的右子树与右子树的左子树

3. 路径总和问题

def hasPathSum(root, targetSum):
    if not root:  # 空树无法满足任何路径和
        return False
    if not root.left and not root.right:  # 叶子节点
        return root.val == targetSum
    # 在左右子树中寻找剩余的和
    remaining = targetSum - root.val
    return (hasPathSum(root.left, remaining) or 
            hasPathSum(root.right, remaining))

变种问题：

• 返回所有满足条件的路径
• 计算路径总数
• 找出路径和最大的路径

递归DFS的优缺点

优点：

1. 代码简洁直观：

   • 直接反映问题的数学定义
   • 接近数学归纳法的思维模式

2. 天然适合树结构：

   • 树本身就是递归定义的数据结构
   • 完美匹配树的分形特性

3. 易于理解和实现：

   • 对于许多树问题，递归解法是最自然的解决方案
   • 通常比迭代实现更易于阅读和维护

4. 分治策略：

   • 自动将问题分解为子问题
   • 简化复杂问题的处理

缺点：

1. 堆栈空间消耗：

   • 每次递归调用都会消耗栈空间
   • 对于深度很大的树（如退化为链表的树），可能导致栈溢出

2. 效率问题：

   • 函数调用开销比迭代大
   • 可能重复计算相同子问题（如计算二叉树直径时）

3. 调试难度：

   • 递归调用栈可能很深，调试时不易跟踪
   • 逻辑错误可能导致无限递归

4. 语言限制：

   • 某些语言对递归深度有限制
   • 不是所有编程环境都优化了递归调用

性能优化建议

1. 尾递归优化：

   • 某些语言（如Scheme）支持尾递归优化
   • 可以将递归改写为尾递归形式减少栈消耗

2. 迭代实现：

   • 对于深度可能很大的树，考虑使用显式栈的迭代方法
   • 迭代DFS的空间复杂度也是O(h)，但常数因子更小

3. 记忆化（Memoization）：

   • 缓存已计算的子问题结果
   • 适用于有重叠子问题的情况（如斐波那契数列）

4. 剪枝策略：

   • 在搜索过程中提前终止不必要的递归分支
   • 如路径和问题中，当当前路径和已超过目标时可以提前返回

5. 广度优先搜索（BFS）替代：

   • 对于寻找最短路径等问题，BFS可能更合适
   • BFS通常使用队列实现，不会出现栈溢出问题

递归实现的DFS是理解和处理二叉树问题的基础，掌握这些基本模式对于解决更复杂的树相关问题（如二叉树的序列化、最近公共祖先、二叉树转换等）至关重要。理解递归在树遍历中的应用，也有助于理解更复杂的递归算法和分治策略。