二叉树递归解题时，如何判断是否需要使用辅助方法

问题描述 #

我不确定在解决二叉树递归问题时，何时需要使用辅助方法，何时不需要。例如，在二叉树的最近公共祖先问题中，代码可以无需辅助方法实现；而在平衡二叉树问题中则需要使用辅助方法。请问该如何区分这两种场景？

我的最近公共祖先问题解法 #

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;
    }
    if(right == null && left == null) {
        return null;
    }
    if(right != null && left == null){
        return right;
    }else{
        return left;
    }
}

平衡二叉树问题的解法示例 #

class Solution {
    boolean bal = true;
    public boolean isBalanced(TreeNode root) {
        maxHeight(root);
        return bal;
    }
    public int maxHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = maxHeight(root.left);
        int right = maxHeight(root.right);

        int diff = Math.abs(left - right);

        if(diff > 1){
            bal = false;
        }
        return Math.max(left, right)+1;
    }
}

场景区分分析 #

1. 无需辅助方法的场景：递归返回值直接匹配问题需求 #

最近公共祖先问题中，递归函数lowestCommonAncestor的返回值完全对应我们最终要的结果：

• 当前节点是p或q时，直接返回该节点，作为当前子树的LCA候选；
• 左右子树递归结果都不为空，说明当前节点就是LCA；
• 只有一侧结果非空，就把该结果向上传递，继续寻找上层的LCA。

整个递归流程里，函数返回值既承担了传递结果的作用，又完成了逻辑判断，不需要额外方法或变量辅助。

2. 需要辅助方法的场景：递归需处理多类型信息或拆分职责 #

平衡二叉树的核心需求是判断树是否平衡，但递归过程中我们既要计算子树高度，又要检查平衡状态：

• 如果只用一个递归函数，它要么返回高度值（无法直接给出平衡判断结果），要么返回布尔值（无法完成高度计算）；
• 辅助方法maxHeight专注于计算子树高度，同时在计算时检查左右高度差，通过全局变量bal记录平衡状态；
• 主函数isBalanced只需要调用辅助方法，最后返回记录的状态即可。

简言之，当递归需要同时处理两种不同类型的信息（比如数值型高度+布尔型平衡状态），单个函数的返回值无法兼顾时，就需要用辅助方法拆分职责。

总结判断标准 #

• 无需辅助方法：递归函数的返回值可以直接传递问题所需结果，每一层递归的逻辑都能通过返回值完成判断和向上传递信息。
• 需要辅助方法：
  • 递归需返回的信息类型与问题最终结果类型不一致；
  • 问题需要同时追踪多个状态，单个函数无法兼顾；
  • 希望拆分逻辑，让主函数专注于入口控制，辅助函数专注于核心递归计算。

内容的提问来源于stack exchange，提问作者goober