如何避免在遞回中使用全域/類級變數？

如果方法不斷使用/更新全域變數，遞回解決方案變得容易，但是當您需要將該變數傳遞到遞回堆疊時，它變得復雜。

以下是 leetcode 問題250的遞回解決方案（java）。計算 Univalue Subtrees。

您可以參考問題以更好地理解。我的解決方案作業得很好。我想避免使用全域變數。

問題陳述：

給定二叉樹的根，回傳單值子樹的數量。單值子樹意味著子樹的所有節點都具有相同的值。

• 示例 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)，類變數uniCount根據一些約束進行更新。

我怎樣才能擺脫使用這個全域變數并想出一個解決方案recurseAndUpdate(TreeNode root, int uniCount)？如何推匯出這種傾向于在嵌套遞回呼叫中傳遞一些值的遞回邏輯的方法？

uj5u.com熱心網友回復：

您的遞回函式當前回傳一個布林值來指示子樹是否是單調的。相反，您可以讓它回傳該子樹中單調子樹的數量，并在它本身不是單調子樹時將該數字設為負數。

這樣你就有了一個遞回函式，它在一個包中回傳兩個資訊：

• 非負數表示子樹是單調的（或空的）并且由那么多節點組成。

• 負數表示子樹不是單調的，并且有很多（絕對值）單調的子樹。

調整您的代碼以使其像這樣作業并不困難。然后，您的包裝器函式將只需要回傳來自遞回樹頂部呼叫的值的絕對值。

我試了一下，但我確實減少了一些代碼——避免代碼重復：

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

uj5u.com熱心網友回復：

您可以先為您的計數器定義一個類，然后輕松地將其傳遞給遞回函式。例如如下：

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

標籤：爪哇 算法 递归 二叉树

上一篇：有沒有辦法在用戶輸入串列中找到最有可能成為下一個的數字？

下一篇：漸近符號的使用