Условно считая узлы в обходе дерева - рекурсивно

Question

Работа над университетским заданием, которое требует сравнения узлов в дереве и подсчета узлов, которые удовлетворяют определенному условию. Я могу видеть, как я мог бы сделать это итеративно, обходя дерево со стеком и т. Д. c, но я уверен, что лекторы ищут рекурсивное решение, и я изо всех сил пытаюсь обдумать эту конкретную реализацию.

Моя текущая (ошибочная) реализация:

public int traverseIncrement(User user, User reference) {

    if(user == null)
        return 0;

    int count = 1;

    if (user.getLeft() != null) {
        if(user.getLevel() > reference.getLevel()) {
            count += traverseIncrement(user.getLeft(), reference);
        }
    }

    if (user.getRight() != null) {
        if(user.getLevel() > reference.getLevel()) {
            count += traverseIncrement(user.getRight(), reference);
        }
    }

    return count;       
}

Есть две очевидные проблемы: первая заключается в том, что первый узел никогда не оценивается, а вторая - в том, что я всегда на единицу выше требуемого вывод. Любой толчок в правильном направлении будет полезен!

Answer 1

Я думаю, что две проблемы связаны. Вместо того, чтобы предполагать, что count равно 1, затем выполнить рекурсию в зависимости от того, выполнено ли условие, следует установить count в зависимости от условия, а затем выполнить рекурсию. Другими словами, оставьте оценку данного узла до вызова, который обрабатывает этот узел.

Кроме того, вы можете отменить проверку для левого или правого значения null, так как ваша функция уже проверяет вход.

public int traverseIncrement(User user, User reference) {
    if(user == null)
        return 0;

    int count = (user.GetLevel() > reference.getLevel()) ? 1 : 0;

    count += traverseIncrement(user.getLeft(), reference);
    count += traverseIncrement(user.getRight(), reference);

    return count;
}