递归返回值使用模式总结

递归返回值的核心作用

递归返回值主要有以下几种使用模式：

1. 传递结果型返回值

特点：返回值直接就是最终结果

场景示例：

// 二叉树的最大深度
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1; // 返回值就是深度结果
}

// 斐波那契数列
public int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2); // 直接返回计算结果
}

适用场景：计算数值结果、判断布尔条件、返回对象等

2. 状态标记型返回值

特点：返回值作为状态标志，配合全局变量或参数使用

场景示例：

// 二叉树的最近公共祖先（LCA问题）
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (root == p || root == q) return root; // 返回找到的节点作为标记
    
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    if (left != null && right != null) return root; // 组合状态判断
    return left != null ? left : right; // 传递状态
}

适用场景：查找问题、路径判断、状态传递

3. 辅助计算型返回值

特点：返回值用于辅助主逻辑，不是最终结果

场景示例：

// 平衡二叉树判断（返回高度辅助判断）
private int checkBalance(TreeNode root) {
    if (root == null) return 0;
    
    int left = checkBalance(root.left);
    if (left == -1) return -1; // 用-1标记不平衡
    
    int right = checkBalance(root.right);
    if (right == -1) return -1;
    
    if (Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1; // 返回高度辅助上层判断
}

public boolean isBalanced(TreeNode root) {
    return checkBalance(root) != -1;
}

适用场景：需要中间计算结果的复杂判断

4. 累积型返回值

特点：返回值在递归过程中不断累积

场景示例：

// 路径总和（累积路径值）
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    
    // 叶子节点且路径和等于目标值
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    
    // 累积减去当前值，传递给子树
    return hasPathSum(root.left, targetSum - root.val) || 
           hasPathSum(root.right, targetSum - root.val);
}

适用场景：路径和、累积计算、参数传递

5. 构造型返回值

特点：返回值是新建的数据结构

场景示例：

// 根据遍历序列构建二叉树
public TreeNode buildTree(int[] preorder, int[] inorder) {
    return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
}

private TreeNode build(int[] preorder, int preStart, int preEnd, 
                      int[] inorder, int inStart, int inEnd) {
    if (preStart > preEnd) return null;
    
    TreeNode root = new TreeNode(preorder[preStart]); // 构造新节点
    // ... 递归构造左右子树
    return root; // 返回构造的树
}

适用场景：构建数据结构、复制结构、生成结果

6. 多信息返回型

特点：需要返回多个信息时，使用自定义类或数组

场景示例：

// 返回二叉树直径和高度
class Result {
    int diameter;
    int height;
    Result(int d, int h) { diameter = d; height = h; }
}

private Result diameterHelper(TreeNode root) {
    if (root == null) return new Result(0, 0);
    
    Result left = diameterHelper(root.left);
    Result right = diameterHelper(root.right);
    
    int diameter = Math.max(Math.max(left.diameter, right.diameter), 
                           left.height + right.height);
    int height = Math.max(left.height, right.height) + 1;
    
    return new Result(diameter, height);
}

适用场景：需要多个返回值的情况

选择返回值类型的决策流程

text

是否需要最终结果？
├── 是 → 传递结果型
└── 否 → 
    ├── 需要状态标记？ → 状态标记型
    ├── 需要辅助计算？ → 辅助计算型  
    ├── 需要累积传递？ → 累积型
    ├── 需要构建结构？ → 构造型
    └── 需要多个信息？ → 多信息返回型

关键原则

1. 一致性：递归函数的返回值含义要一致
2. 简洁性：能用简单类型就不要用复杂结构
3. 有效性：避免不必要的返回值传递
4. 可读性：返回值要能清晰表达意图

理解这些模式后，面对新的递归问题时，就能快速判断应该采用哪种返回值策略。