Почему "res" не меняется в моей функции DFS?

У меня есть следующий код для вычисления глубины дерева:

class Solution {
    public int maxDepth(TreeNode root) {
        int res = 0;
        DFS(root, res, 1);
        return res;
    }
    private void DFS(TreeNode root, int res, int curDepth) {
        if (root == null) {
            return; 
        }

        if (curDepth > res) {
            res = curDepth;
        }
        DFS(root.left, res, curDepth + 1);
        DFS(root.right, res, curDepth + 1);
    }
}

Если я дам ему вход [3, 9, 20, null, null, 15, 7], я ожидаю, что res будет равен 3, так как он представляет глубину двоичного дерева. Но res оказывается равным нулю. Кажется, что ничего не изменилось.

Кто-нибудь знает почему?

Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
0
76
2

Ответы 2

Помните, что на языке, который вы используете (я думаю, это Java?), Параметры функций - передается по значению. Это означает, что когда вы пишете

DFS(root, res, 1)

на самом деле вы не берете переменную res и не передаете ее функции DFS для изменения. Вместо этого вы говорите «сделайте копию любого значения, которое хранится в переменной с именем res, а затем передайте эту копию DFS».

Метод DFS имеет параметр с именем res, но тот факт, что он называется res и что у вас есть собственная переменная с именем res в maxDepth, не означает, что эти значения связаны. Например, однажды я проводил свой класс с шестью учениками по имени Зоя (реальная история!). Хотя всех звали Зоя, они определенно не были одним и тем же человеком! Я не мог поговорить с одним человеком по имени Зои и ожидать, что все остальные Зои хоть немного поймут, о чем мы говорили. Таким же образом ваша переменная res в maxDepth полностью отделена от переменной res в DFS. По совпадению у них одно и то же имя, но это не одно и то же лицо.

Есть несколько способов исправить это, и, вероятно, лучший способ сделать это - заставить DFS вернуть вам значение, а затем написать свой код следующим образом:

public int maxDepth(TreeNode root) {
    return DFS(root, 1);
}

private int DFS(TreeNode root, int currDepth) {
    // For you to figure out!
}

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

Вау, спасибо большое ! Ваше объяснение потрясающее.

Morty 01.08.2018 17:11

Если вы хотите вычислить высоту узла, вам нужно просто добавить единицу к максимуму высоты левого и правого дерева. Если узел не существует, он не имеет высоты.

private int height(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return 1 + Math.max(height(node.left), height(node.right));
}

Причина, по которой ваше решение не работает, заключается в том, что значение res передается по значению, как указано в templatetypedef.

На самом деле вам не нужен параметр с глубиной, чтобы решить эту проблему.

Другие вопросы по теме