Можно ли написать алгоритм, который принимает двоичное дерево T и возвращает целочисленное значение, представляющее высоту T

Question

Итак, я сейчас читаю структуры данных и алгоритмы в Java Шестом издании, и одно из упражнений в книге гласит:

Запись алгоритма, который принимает двоичное дерево T и возвращает целое число значение, которое представляет высоту T. Напомним, что высота двоичного дерева - это число ребер между root дерева и его самым дальним листом. Например, следующее дерево имеет высоту 3:

Дерево выглядит следующим образом:

                           A
                          / \
                         B   C
                        / \   \
                       D   E   F
                                \
                                 G

Теперь, если кто-нибудь может дать несколько указателей о том, как я должен его запустить, это будет быть фантазийным c, потому что в данный момент я борюсь с этим упражнением.

Заранее большое спасибо.

Редактировать: Я прошу прощения, я полностью забыл поставить свой псевдокод, здесь это:

Algorithm Total_Height (L_subtree, R_subtree, root)
Total_Height (root) {
    If (root == null)
        Return – 1
    Return max (Total_Height( root-> L_subtree), Total_Height (root-> R_subtree))
}

Будем весьма благодарны за любые замечания или улучшения, которые могут быть сделаны.

Answer 1

Чтобы получить «высоту» дерева, вы должны отслеживать глубину, в которой вы находитесь:

int Tree_Height(root, depth) {
    if (root == null) {
        return -1;
    }
    return max(
        Tree_Height(root.L_subtree, depth + 1),
        Tree_Height(root.R_subtree, depth + 1),
        depth
    );
}

Вам нужна глубина в функции max, потому что в конце для дерева результат будет -1, который будет распространяться на вершину, а общий результат от функции будет -1. Если вы не поняли это объяснение, попробуйте следить за выполнением вашей программы на листе бумаги. Это всегда полезно при исправлении ошибок в рекурсии.