java - 如何避免在递归中使用全局/类级别变量？

Question

如果方法不断使用/更新全局变量，递归解决方案就会变得很容易，但当您需要将该变量传递到递归堆栈时，递归解决方案就会变得复杂。

以下是leetcode问题的递归解决方案(java)250. Count Univalue Subtrees .

您可以引用该问题以更好地理解。我的解决方案效果很好。我想避免使用全局变量。

问题陈述:

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

• 示例 1

输入:root = [5,1,5,5,5,null,5] 输出:4

• 示例 2

输入:root = [] 输出:0

• 示例 3

输入:root = [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)中，类变量uniCount正在根据一些约束进行更新。

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

Answer 1

您的递归函数当前返回一个 boolean 值来指示子树是否单调。相反，您可以让它返回该子树中单调子树的数量，并且当它本身不是单调子树时，使该数字负。

这样你就可以使用递归函数在一个包中返回两个信息:

• 非负数表示子树是单调(或空)并且由那么多节点组成。

• 负数表示子树不是单调的，并且有很多(绝对值)单调子树。

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

我尝试过，但我确实减少了代码——避免代码重复:

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