java - 如何计算 BST 中级别的总和

Question

我已经摸不着头脑几个小时了，想不通。我需要创建一个方法来“计算树中节点级别的总和”，但我的方法一直返回 0。

我已经使用调试器多次调试它，开始时一切正常，但当它到达方法的底部时，它返回 lvl 并重置回 0。

如果有人能帮助我理解为什么会这样，我将不胜感激。谢谢

    public int sumOfLevels() {
    return sumOfLevels(_root, 0);
}

private int sumOfLevels(Node node, int lvl) {
    if (node == null)
        return lvl;
    sumOfLevels(node.right, lvl);
    lvl += findLevel(node.data);
    sumOfLevels(node.left, lvl);

    return lvl;
}

Answer 1

您不需要 findLevel() 函数来计算每个递归调用的级别，这是非常低效的。只需将当前级别作为参数传递即可。像这样:

private int sumOfLevels(Node node, int currentlvl) {
    if (node == null)
        return 0;
    else {
        int sum = currentlvl;
        sum += sumOfLevels(node.right, currentlvl + 1);
        sum += sumOfLevels(node.left, currentlvl + 1);
        return sum;
    }
}