为什么静态成员变量不适用于递归方法中的保留值？

Question

当我尝试在 LeetCode OJ 上解决 "Sum of Left Leaves" 树问题时，我观察到如下问题：

给定一个示例树，只有两个左叶子节点8和9，期望答案是17，完整的树可以参考下面的主要方法。

我首先写的错误答案是使用静态成员变量"sum" 来存储当前递归的结果并作为参数传递给下一个递归。但是如下代码，它总是 return 0.

public class Solution {
   public TreeNode root;

   private static class TreeNode {
      private String val;
      private TreeNode left, right;
      public TreeNode(String x) {
         this.val = x;
      }
   }

   public static int sum = 0;
   public static int sumOfLeftLeaves(TreeNode root) {
      if(root == null) {
         return 0;
      }

      sumOfLeftLeavesRec(root, false, sum);
      return sum;
   }

   public static void sumOfLeftLeavesRec(TreeNode x, boolean isLeft, int sum) {
      if(x == null) {
          return;
      }

      if(x.left == null && x.right == null && isLeft) {
          sum += Integer.valueOf(x.val);
      }

      sumOfLeftLeavesRec(x.left, true, sum);
      // As debug model check, if just use static memeber variable sum could not
      // keep the value when return from deepest recursion, e.g when return from
      // node 8, the sum should be 8 and pass into new recursion on node 6(which
      // return from recursion of node 8), but real situation is sum will change
      // back to 0.
      sumOfLeftLeavesRec(x.right, false, sum);
   }

   public static void main(String[] args) {
     /*
      * The tree used for test
      *        1
      *      /   \
      *     2     3
      *    / \   /
      *   6   5 9
      *  /
      * 8
     */
     Solution s = new Solution();
     s.root = new TreeNode("1");
     s.root.left = new TreeNode("2");
     s.root.right = new TreeNode("3");
     s.root.left.left = new TreeNode("6");
     s.root.left.right = new TreeNode("5");
     s.root.left.left.left = new TreeNode("8");
     s.root.right.left = new TreeNode("9");

     int result = sumOfLeftLeaves(s.root);
     System.out.println(result);
   }
}

我在这个 site 第二个解决方案 Java 版本上观察到的正确答案。它生成一个新的 class 作为 "Summ" 并使用其成员变量 "sum" 来存储结果并将结果传递给下一个递归，并且在我测试时它工作正常（下面的代码）。主要方法和示例树是一样的

public class Solution {
   private class Accumulator{
      int sum = 0;
   }

   public int sumOfLeftLeaves(TreeNode root) {
      if(root == null) {
          return 0;
      }

      Accumulator accumulator = new Accumulator();

      sumOfLeftLeavesRec(root, false, accumulator);
      return accumulator.sum;
   }

   /* Pass in a sum variable as an accumulator */
   public void sumOfLeftLeavesRec(TreeNode x, boolean isLeft, Accumulator accumulator) {
      if(x == null) {
          return;
      }

      if(x.left == null && x.right == null && isLeft) {
          accumulator.sum += x.val;
      }

      sumOfLeftLeavesRec(x.left, true, accumulator);
      sumOfLeftLeavesRec(x.right, false, accumulator);
   }
}

问题是为什么静态成员变量在这种情况下不起作用，另外，为什么要创建一个新的嵌套class因为"Accumulator"可以用于记录并成功传递"sum"结果？机械上，临界点是什么？谢谢

Answer 1

Why static member variable not work for retain value in recursive method?

事实上，问题不在于 sum 是静态的（虽然 static sum 是一个坏主意......）

问题是在这段代码中：

public static void sumOfLeftLeavesRec(TreeNode x, boolean isLeft, int sum) {
    if(x == null) {
        return;
    }

    if(x.left == null && x.right == null && isLeft) {
        sum += Integer.valueOf(x.val);
    }
    ...
 }

sum 变量不是静态的。它是一个局部变量。因此，您正在做的是计算局部变量 中的部分和，然后在每次 sumOfLeftLeavesRec 调用结束时将其丢弃 。

您需要回到最初的问题陈述，并弄清楚信息需要如何在递归调用之间流动。

提示：设计简单递归算法的正常方法是将信息作为调用参数传递，return它作为通话结果。这应该在这里工作。

Answer 2

在您的情况下，您创建整数变量 sum 它是原始且不可变的。您将此不可变变量作为参数传递，因此静态变量 sum 不会更新，因此删除参数 sum。试试这个。

    public class Solution {
  public TreeNode root;

  private static class TreeNode {
    private String val;
    private TreeNode left, right;

    public TreeNode(String x) {
      this.val = x;
    }
  }

  public static int sum = 0;

  public static int sumOfLeftLeaves(TreeNode root) {
    if (root == null) {
      return 0;
    }

    sumOfLeftLeavesRec(root, false);
    return sum;
  }

  public static void sumOfLeftLeavesRec(TreeNode x, boolean isLeft) {
    if (x == null) {
      return;
    }

    if (x.left == null && x.right == null && isLeft) {
      sum += Integer.valueOf(x.val);
    }

    sumOfLeftLeavesRec(x.left, true);
    // As debug model check, if just use static memeber variable sum could not
    // keep the value when return from deepest recursion, e.g when return from
    // node 8, the sum should be 8 and pass into new recursion on node 6(which
    // return from recursion of node 8), but real situation is sum will change
    // back to 0.
    sumOfLeftLeavesRec(x.right, false);
  }

  public static void main(String[] args) {
     /*
      * The tree used for test
      *        1
      *      /   \
      *     2     3
      *    / \   /
      *   6   5 9
      *  /
      * 8
     */
    Solution s = new Solution();
    s.root = new TreeNode("1");
    s.root.left = new TreeNode("2");
    s.root.right = new TreeNode("3");
    s.root.left.left = new TreeNode("6");
    s.root.left.right = new TreeNode("5");
    s.root.left.left.left = new TreeNode("8");
    s.root.right.left = new TreeNode("9");

    int result = sumOfLeftLeaves(s.root);
    System.out.println(result);
  }
}

为什么静态成员变量不适用于递归方法中的保留值？

Why static member variable not work for retain value in recursive method?

java

algorithm

recursion

pass-by-value