Как я могу вычислить сумму уровней в 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;
    }
}