计算二叉树中所有节点的节点深度

Question

我正在尝试解决Algoexpert 的节点深度问题。该问题要求您计算给定二叉树中所有节点的深度总和。例如，给定这棵树 -

          1
       /     \
      2       3
    /   \   /   \
   4     5 6     7
 /   \
8     9

总和应该是 16。

我为其编写了一个递归解决方案，我认为这是正确的，但有趣的是，只有第一个测试通过，而其余测试用例失败。这是我的解决方案-

import java.util.*;

class Program {

  // static variable to hold the final sum
  private static int finalSum = 0;

  public static int nodeDepths(BinaryTree root) {
        // Write your code here.
        int runningSum = 0;
        depthHelper(root.left, runningSum);
        depthHelper(root.right, runningSum);
        return finalSum;
  }
    
    private static void depthHelper(BinaryTree node, int runningSum) {
        if(node == null) return;
        runningSum++;
        finalSum += runningSum;
        depthHelper(node.left, runningSum); 
        depthHelper(node.right, runningSum);
    }

  static class BinaryTree {
    int value;
    BinaryTree left;
    BinaryTree right;

    public BinaryTree(int value) {
      this.value = value;
      left = null;
      right = null;
    }
  }
}

该算法本身相当简单。

有一个runningSum变量（初始化为 -1 以说明根），每次访问新节点（即：比其父节点低一级）时，我都会向该变量添加 1。并且，该变量的值runningSum会在每次递归调用时添加到该finalSum变量中。

例如，在节点 2 处，runningSumis 1，并且 this 被添加到finalSumwhich was 0。现在finalSum变成了1。节点相同3，之后finalSum变为2。在节点处4，runningSum成为2并finalSum成为4。

第一个测试用例通过，我收到此消息 -

但随后，所有的案例都失败了。我认为可能发生的情况是- 先前测试用例执行的输出未清除，并且以某种方式添加到当前测试用例执行的结果中。

这就是为什么我认为这可能是原因 -

 1. Test case 2 - our code output - 0,  your code output - 16
 2. Test case 3 - our code output - 1,  your code output - 17
 3. Test case 4 - our code output - 2,  your code output - 19
 4. Test case 5 - our code output - 4,  your code output - 23
 5. Test case 6 - our code output - 21,  your code output - 44
 6. Test case 7 - our code output - 42,  your code output - 86

请注意，先前执行的结果不会被清除，而是会添加到后续执行的“我们的代码输出”中。例如，在第二个测试用例中，“您的代码输出”结果显示16哪个实际上是第一个测试用例的结果。

这是由于static在代码中使用了全局变量吗？但我在 Leetcode 上多次使用过同样的方法，而且效果很好。

或者我的算法中是否存在不同的错误？

PS - 我知道在这里使用屏幕截图是不受欢迎的，但这有可能是一个特定于平台的问题，所以我不得不使用它。

Answer 1

在我看来，这种行为的发生并不是一个错误。这是因为使一切都是静态的。有很多可能性可以避免这个问题。其中两个在这里解释：

使用静态方法但使用无状态类：

public static int nodeDepths(BinaryTree root) {
    // Write your code here.
    return depthHelper(root.left, 1) + depthHelper(root.right, 1);
}

private static int depthHelper(BinaryTree node, int sum) {
    if (node == null) return 0;
    return sum + depthHelper(node.left, sum + 1) + depthHelper(node.right, sum + 1);
}

创建一个对象（如果您不只对对象执行一项操作，则会变得更有用）：

public static int nodeDepths(BinaryTree root) {
    // Write your code here.
    return new Program().depthSum(root); // call to non-static method
    // like this you can use your original implementation, but the
    // class variable (finalSum) has to be non-static too
}

两种实现都是线程安全的。