У меня есть следующий код для вычисления глубины дерева:
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
оказывается равным нулю. Кажется, что ничего не изменилось.
Кто-нибудь знает почему?
Помните, что на языке, который вы используете (я думаю, это 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 и какие обновления вам нужно будет внести в него, чтобы эта информация распространялась должным образом.
Если вы хотите вычислить высоту узла, вам нужно просто добавить единицу к максимуму высоты левого и правого дерева. Если узел не существует, он не имеет высоты.
private int height(TreeNode node) {
if (node == null) {
return 0;
}
return 1 + Math.max(height(node.left), height(node.right));
}
Причина, по которой ваше решение не работает, заключается в том, что значение res
передается по значению, как указано в templatetypedef.
На самом деле вам не нужен параметр с глубиной, чтобы решить эту проблему.
Вау, спасибо большое ! Ваше объяснение потрясающее.