Привет, я натолкнулся на код, чтобы найти максимальную высоту двоичного дерева. В этом коде зачем +1 в операторе возврата?Максимальная высота двоичного дерева
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
Если не было, то результат всегда будет 0.
Максимальная высота бинарного дерева максимальная высота ребенка, имеющего большую максимальную высоту (это Math.max(maxDepth(root.left), maxDepth(root.right)) часть) + 1 для корня дерева.
Рассмотрите дерево, состоящее из одного корневого узла. Тогда следующий оператор возврата будет возвращать 1, который является то, что мы ожидаем:
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
return Math.max(0, 0) + 1;
return 1;
Как ваш базовый случай показывает, пустое дерево будет иметь высоту нуля, и вы можете построить до высоты с помощью индукции более высоких деревьев ,
Чтобы скопировать значение глубины, когда рекурсивная логика опускается до тех пор, пока листья дерева не будут установлены. – janos
Узел имеет два под дерева, слева и справа. Высота узла - это высота слева или справа, в зависимости от того, что больше, плюс сам узел, следовательно +1. Это должно быть довольно прямолинейно. Например, есть узел. Его левое дерево имеет высоту 10, правое дерево имеет высоту 7. Тогда высота самого узла составляет 10 плюс еще один уровень для себя, что дает 11 –