java 在递归中何时使用helper方法

lc8prwob 于 5个月前发布在 Java

关注(0)|答案(2)|浏览(51)

我不知道什么时候使用辅助方法来解决二叉树中的递归问题，什么时候不使用。例如，在二叉树的最低共同祖先中，代码可以在没有辅助方法的情况下完成（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没有。提前谢谢你。

Java

来源：https://stackoverflow.com/questions/77738084/when-to-use-helper-method-in-recursion

2条答案

按热度按时间

oxcyiej71#

答案有多个方面：

递归从来都不是必需的。
但是有一种非常常见的使用助手的方式。

不需要递归。

你永远不需要递归。每一个递归的解决方案都可以简单地重写为一个使用一个循环的解决方案。这里，本质上，它是如何工作的：（作为一个例子，我们使用Fibonacci，递归的万年青教科书例子，非递归的解决方案是不必要的复杂;这些例子的重点是展示如何重写任何递归算法！）

// recursive function:

void fibR(int n) {
  return switch (n) {
    case 0 -> 0;
    case 1, 2 -> 1;
    default -> fibR(n-2) + fibR(n-1);
  };
}

// loop rewrite:

static class FibJob {
  int n;
  FibJob(int n) {this.n = n;}
}

int fibL(int n) {
  var jobs = new ArrayDeque<FibJob>();
  jobs.add(new FibJob(n));

  int total = 0;
  while (!jobs.isEmpty()) {
    FibJob job = jobs.pollFirst();
    switch (job.n) {
      case 0 -> total += 0;
      case 1, 2 -> total += 1;
      default -> {
        jobs.add(new FibJob(job.n - 2));
        jobs.add(new FibJob(job.n - 1));
      }
    };
  }

  return total;
}

字符串
注意：这段代码错过了一些重要的优化，当然，使用FibJob对象只存储单个int值是一个不必要的复杂性，但它展示了如何将其应用于具有多个输入值的递归算法。

Helper方法

递归作为一个概念涉及：
一种算法，它接受一些参数，并使用[A]这些参数和[B] 1个或多个对自身的调用进行非常简单的计算，但参数向“更简单”的值移动。此外，该算法将不递归地回答最简单的可能值（“基本情况”）。
帮助器方法自然出现的关键点在于如何将信息从一个调用传递到下一个调用。例如，对于fib，它真实的简单-唯一需要传入的参数是您想要的值（例如，“I want the 8 th Fibonacci number”中的“8”），唯一需要传递“back”的值是结果。
这和最初的问题完全相同。这就是为什么你很少看到帮助方法出现的原因，例如fib的递归实现。
还有其他递归算法，其中传递的内容和通常声明的内容之间不匹配。
例如，假设一个路径查找算法试图找到A和Z之间的最短路径，给定一个大的“图”，列出字母之间存在哪些道路，以及它们的长度。假设所有道路总是从前面的字母到后面的字母（总是从A到C，从来没有从C到A），那么我们可以应用递归算法：

Map<Character, Map<Character, Integer>> graph = ...;

int navigate(char from, int soFar) {
  if (from == 'Z') return soFar;
  Map<Character, Integer> destinations = graph.getOrDefault(from, Map.of());
  int minimum = Integer.MAX_VALUE;
  for (var entry : destinations.entrySet()) {
    int kmsToDestination = entry.getValue();
    char destination = entry.getKey();
    minimum = Math.min(navigate(destination, soFar + kmsToDestination));
  }
  return minimum;
}

型
这个算法只有一个问题：调用者并不真正理解为什么soFar作为一个参数存在。这对这个特定的算法至关重要，但当从“外部”看这个算法时，它是一个实现细节。调用者真的只是想：嘿，我在C，如果我想到达Z，最短的公里数是多少？他们只想告诉你“C”。他们不想告诉你：哦，我们开始了，所以我们的里程表上到目前为止是0公里。
因此，helper方法：

int navigate(char from) {
  return navigate(from, 0);
}

型
这些helper实际上总是传递一堆“unit”（基本）值作为附加参数：0（用于加法算法），1（用于乘法），或空列表/集合/Map，或空字符串。
当然，helper仍然不是必需的，只是，很好：你并不真的想向调用者解释这个soFar的存在以及它的目的是什么。调用者不太可能想要这个功能，它只会让人感到困惑。

赞(0）回复(0）举报 5个月前

tktrz96b2#

如果你需要反复调用一些函数，那么你需要一个单独的函数。
这是因为Leetcode提供的原始函数不能被重复调用，因为它不适合你的需求。如果你改变它的签名，Leetcode将无法调用它。
你分享的第二段代码有一个递归算法。因此需要写一个递归（帮助）函数。main函数只需要弄清楚传递给帮助函数的正确值。
在这种情况下，它只是碰巧是root。通常它是root，并传递一个currentValue。就像节点到该节点的总和。或者其他东西。如果你再次从根开始，那么总和将只是根值本身。

赞(0）回复(0）举报 5个月前

我来回答

java 在递归中何时使用helper方法

2条答案

不需要递归。

Helper方法

相关问题

热门标签

最新问答