如何避免在递归中使用 global/class 级变量？

Question

如果方法保留 using/updating 全局变量，递归解决方案会变得简单，但当您需要将该变量传递到递归堆栈时，它会变得复杂。

以下是一个 leetcode 问题 250. Count Univalue Subtrees.

的递归解决方案（java）

您可以参考问题，以便更好地理解。我的解决方案工作得很好。我想避免使用全局变量。

问题陈述：

给定二叉树的根，return单值子树的数量。单值子树意味着子树的所有节点都具有相同的值。

示例 1

输入：根=[5,1,5,5,5,null,5] 输出：4

示例 2

输入：根=[] 输出：0

示例 3

输入：根=[5,5,5,5,5,null,5] 输出：6

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {

  int uniCount; // class level variable to keep the count of uni-valued tree/sub-tree

  public int countUnivalSubtrees(TreeNode root) {
    uniCount = 0;
    recurseAndUpdate(root);
    return uniCount;
  }


  private boolean recurseAndUpdate(TreeNode root) {

    if (root == null) {
      return true;
    }

    if (root.left == null && root.right == null) { // If root is a leaf node
      uniCount++;
      return true;
    } else if (root.left == null && root.right != null) { // If root has only right child
      boolean currRes = root.val == root.right.val;
      boolean rightRes = recurseAndUpdate(root.right);

      if (currRes && rightRes) {
        uniCount++;
        return true;
      }

    } else if (root.left != null && root.right == null) { // If root has only left child

      boolean currRes = root.val == root.left.val;
      boolean leftRes = recurseAndUpdate(root.left);

      if (currRes && leftRes) {
        uniCount++;
        return true;
      }

    } else { // If root have both the left & right child

      boolean currRes = root.val == root.left.val && root.val == root.right.val;
      boolean leftRes = recurseAndUpdate(root.left);
      boolean rightRes = recurseAndUpdate(root.right);

      if (currRes && leftRes && rightRes) {
        uniCount++;
        return true;
      }

    }

    return false;

  }

}

在上面的递归函数 recurseAndUpdate(TreeNode root) 中，class 变量 uniCount 正在根据某些约束进行更新。

我怎样才能摆脱使用这个全局变量并提出像 recurseAndUpdate(TreeNode root, int uniCount) 这样的解决方案？如何推导出这种倾向于在嵌套递归调用中传递一些值的递归逻辑的方法？

Answer 1

您可以先为您的计数器定义一个class，然后轻松地将它传递给递归函数。例如如下：

// define a class as a wrapper
class RecursiveCounter {
    int value;
    public RecursiveCounter(){
        value = 0;
   }
}

// modify the current solution class as follows

// remove the global variable

private boolean recurseAndUpdate(TreeNode root, RecursiveCounter uniCount) {
// replace all uniCount to uniCount.value
// Also, pass the same uniCount variable to all recursive calls
// ...
}

public int countUnivalSubtrees(TreeNode root) {
    RecursiveCounter uniCount;
    recurseAndUpdate(root, unitCount);
    return uniCount.value;
}

Answer 2

您的递归函数目前return是一个布尔值，用于指示子树是否单调。您可以改为让它 return 该子树中单调子树的数量，和使该数字 negative 当它本身不是单调子树。

这样你就有了递归函数，return将两个信息放在一个包中：

非负数表示子树是单调的（或空的）并且由那么多节点组成。
负数表示子树不是单调的，并且有那么多（绝对值）子树是单调的。

调整您的代码以使其像那样工作并不难。然后，您的包装函数只需要 return 来自递归树顶部调用的值的绝对值。

我试了一下，但我确实减少了一些代码——避免代码重复：

  public int countUnivalSubtrees(TreeNode root) {
    return Math.abs(recurseAndUpdate(root));
  }

  private int recurseAndUpdate(TreeNode root) {
    if (root == null) {
      return 0;
    }
    boolean current = (root.left == null || root.val == root.left.val) && 
                      (root.right == null || root.val == root.right.val);
    int leftRes = recurseAndUpdate(root.left);
    int rightRes = recurseAndUpdate(root.right);
    return leftRes < 0 || rightRes < 0 || !current 
        ? -Math.abs(leftRes) - Math.abs(rightRes)
        : leftRes + rightRes + 1;
  }

如何避免在递归中使用 global/class 级变量？

How to avoid using global/class level variables in recursion?

java

algorithm

recursion

binary-tree

问题陈述：