何时在递归中使用辅助方法

Question

我不确定何时使用辅助方法来解决二叉树中的递归问题，何时不使用辅助方法。例如，在二叉树的最低公共祖先中，可以在没有辅助方法的情况下完成代码（https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/），而在问题平衡二叉树（https://leetcode.com/problems/balanced-binary-tree/）我们使用辅助方法。如何区分何时使用？

对于我的最低共同祖先，解决方案是这样的：

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;
    }
}

平衡树有辅助方法

maxHeight

，而

lowestCommonAncestor

没有。 预先感谢您。

Answer 1

如果您需要重复调用某个函数，那么您需要一个单独的函数。

这是因为Leetcode提供的原始函数不适合你的需求，不能重复调用。如果你改变了它的签名那么 Leetcode 将无法调用它。

您分享的第二个代码有一个递归算法。因此需要编写一个递归（辅助）函数。主函数只需要弄清楚传递给辅助函数的正确值是什么。