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

Question

When I try to solve a tree problem as "Sum of Left Leaves" on LeetCode OJ, i observe a problem like below:

Given a example tree as only two left leave nodes as 8 and 9, the expecting answer is 17, the full tree can refer to below main method.

The wrong answer I write first is using a static member variable "sum" to store result of current recursion and pass as parameter into next recursion. But as below code, it will always 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);
   }
}

The right answer I observe on this site second solution Java version. Which generate a new class as "Summ" and use its member variable "sum" to store and pass the result to next recursion, and as I test this works fine(Code below). The main method and sample tree are the same.

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

The question is why static member variable not work in this situation, also, why create a new nested class as "Accumulator" can used for record and pass "sum" result successfully ? Mechanically, what is the critical point ? Thanks

Answer 1

In your case you create integer variable sum it is primitive and immutable. You pass this immutable variable as parameter so static variable sum is not update so remove the parameter sum. try this one.

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