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

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

提问人:Lampard 提问时间:11/9/2016 最后编辑:Lampard 更新时间:11/9/2016 访问量:798

问:

当我尝试在 LeetCode OJ 上将树问题解决为“左叶总和”时,我观察到如下问题:

给定一个示例树,只有两个左边的节点分别为 8 和 9,预期答案是 17,完整的树可以参考下面的 main 方法。

我首先写的错误答案是使用静态成员变量“sum”来存储当前递归的结果,并作为参数传递到下一个递归中。但如下代码所示,它将始终返回 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);
   }
}

我在这个网站上观察到的正确答案是第二个解决方案Java版本。它生成一个新类作为“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);
   }
}

问题是为什么静态成员变量在这种情况下不起作用,另外,为什么要创建一个新的嵌套类,因为“累加器”可用于记录并成功传递“总和”结果?从机械上讲,临界点是什么?谢谢

Java 算法 递归 传递值

评论

1赞 Rogue 11/9/2016
static 没有意义,因为这样你就会把自己限制在每个程序的单一树上。重点是 sum 将被计算为一个实例变量/方法,您将调用树的实例
1赞 Jon Skeet 11/9/2016
请花点时间格式化您的代码 - 阅读没有正确缩进的代码真的很难。
0赞 Lampard 11/9/2016
感谢 Rogue 和 Jon Skeet 的建议,已经重新格式化。

答:

1赞 Stephen C 11/9/2016 #1

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

事实上,问题不在于静态的(尽管 a 是个坏主意......sumstatic 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);
    }
    ...
 }

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

您需要回到原始问题陈述,并弄清楚信息需要如何在递归调用之间流动。

提示:设计简单递归算法的正常方法是将信息作为调用参数传递,并将其作为调用结果返回。这应该在这里起作用。

评论

0赞 Lampard 11/9/2016
谢谢,“计算机并扔掉它”正是我在调试模型上观察到的,因为方法“sumOfLeftLeavesRec()”设计为没有返回值,但我仍然对一个问题感到困惑,在正确的解决方案中,如果我们传入一个内部类的实例并使用其成员变量来记录是否成功,那么为什么?
0赞 Stephen C 11/9/2016
假设您在任何地方传递/使用相同的实例来累积状态,则相当于传递一个“共享变量”。它有效。不过有更好的解决方案。
0赞 Lampard 11/9/2016
谢谢你,斯蒂芬,这是有道理的。
0赞 Lampard 11/9/2016
还可以找到一个有价值的答案作为 stackoverflow.com/a/10265620/6706875
0赞 janith1024 11/9/2016 #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);
  }
}

评论

0赞 Lampard 11/9/2016
太棒了,你的输入正是我试图弄清楚的,传递一个不可变的类型类成员变量“sum”对收集结果没有任何帮助,这就是为什么我认为正确的解决方案在可变类型对象的实例中传递为“累加器”(作为 java 按值传递,它实际上是将存储在堆栈点上的值传递给堆上的“累加器”对象, 并且每次都传递相同的值,因此不断更改相同的对象),我也尝试了您指向此处的方式,它工作正常。我认为正确的方法是传入可变对象的实例,或者像您的答案一样使用副作用来记录。