LeetCodeOJで「SumofLeft Leaves」としてツリーの問題を解決しようとすると、次のような問題が発生します。
左の2つのノードのみが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バージョンの2番目のソリューションです。これは「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);
}
}
問題は、なぜ静的メンバー変数がこの状況で機能しないのか、また、「アキュムレータ」がレコードに使用され、「合計」の結果を正常に渡すことができるため、新しいネストされたクラスを作成するのはなぜですか?機械的に、臨界点は何ですか?ありがとう
あなたの場合、整数変数の合計を作成します。それは原始的で不変です。この不変変数をパラメーターとして渡すため、静的変数の合計は更新されないため、パラメーターの合計を削除します。これを試してください。
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);
}
}
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加