静的メンバー変数が再帰的メソッドで値を保持するために機能しないのはなぜですか？

Question

私はLeetCode OJ上の「左葉の合計」として木問題を解決しようとすると、私は以下のような問題を守ってください。

は8と9のように2つだけ左休暇ノードとして例の木を考えると、期待して答えを17であり、フルツリーは以下のメインメソッドを参照することができます。

私が最初に書く間違った答えは、現在の再帰の結果を格納するために静的メンバー変数 "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); 
    } 
} 

私はこのsite第二溶液の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); 
    } 
} 

質問は成功し、「合計」の結果を記録するために使用して渡すことができ、また、なぜ「アキュムレータ」などの新しいネストされたクラスを作成しているのですか？機械的に、重要な点は何ですか？ありがとう

Answer 1

あなたの場合、整数変数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); 
    } 
} 

Answer 2

なぜ静的メンバー変数が再帰的メソッドで値を保持するために機能しないのですか？

実際には、問題が

問題がある（... は悪い考えですが）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コールが終了するとを放棄します。

元の問題ステートメントに戻り、再帰呼び出し間で情報をどのように流す必要があるかを検討する必要があります。

ヒント：単純な再帰アルゴリズムを設計する通常の方法は、呼び出しの引数として情報を渡すと、呼び出し結果としてそれを返すことです。それはここでうまくいくはずです。