0

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

Lampard
  • 394
  • 7
  • 23
  • 1
    static doesn't make sense because then you are limiting yourself to a singular Tree per program. The whole point is sum would be calculated as an instance variable / method, one which you'd call upon an instance of the Tree – Rogue Nov 09 '16 at 02:27
  • 1
    Please take the time to format your code - it's *really* hard to read code that isn't properly indented. – Jon Skeet Nov 09 '16 at 02:31
  • Thank you for Rogue's and Jon Skeet's suggest, already reformat. – Lampard Nov 09 '16 at 02:43

2 Answers2

1

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

In fact, the problem is not that sum is static (though a static sum is a bad idea ...)

The problem is that in this code:

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

the sum variable is NOT static. It is a local variable. So what you are doing is computing a partial sum in a local variable and then throwing it away when each sumOfLeftLeavesRec call ends.

You need to go back to the original problem statement, and work out how the information needs to flow between the recursive calls.

HINT: The normal way to design a simple recursive algorithm is to pass information as call arguments and return it as the call result. That should work here.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • Thank you, "computer and throw it away" is exactly what i observe on debug model, as method "sumOfLeftLeavesRec()" design as no return value, but i am still confused on one question, in right solution, if we pass in an instance of inner class and use its member variable to record is successful, so why ? – Lampard Nov 09 '16 at 03:53
  • Assuming that you pass / use the same instance everywhere to accumulate the state, it is equivalent to a passing around a "shared variable". It works. There are better solutions though. – Stephen C Nov 09 '16 at 04:05
  • Thank you, Stephen, this makes sense. – Lampard Nov 09 '16 at 04:26
  • Also find a valuable answer as http://stackoverflow.com/a/10265620/6706875 – Lampard Nov 09 '16 at 10:05
0

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);
  }
}
janith1024
  • 1,042
  • 3
  • 12
  • 25
  • Awesome, your input is exactly i tried to figure out, pass an immutable type class member variable "sum" helps nothing on collect result, that's why i think the right solution pass in an instance of mutable type object as "accumulator"(as java pass by value, it is actually pass in the value stored on stack point to "accumulator" object on heap, and every time pass in the same value, so continuously change the same object), also I tried the way you point here, it works fine. I think right way is either pass in an instance of mutable object or like your answer use side effect to record. – Lampard Nov 09 '16 at 04:35