Диаметр двоичного дерева — неудачный случай, когда самый длинный путь не проходит через корень
Итак, я работаю над этой проблемой:
Учитывая корень двоичного дерева, верните длину диаметра дерева.
Диаметр двоичного дерева — это длина самого длинного пути между любыми двумя узлами дерева. Этот путь может проходить через корень, а может и не проходить.
Длина пути между двумя узлами представлена количеством ребер между ними.
Вот как я пытался решить:
var diameterOfBinaryTree = function(root) {
if (root === null) return 0;
let max_height = 0;
function maxDepth(node) {
if (node === null) return 0;
var lh = maxDepth(node.left);
var rh = maxDepth(node.right);
return 1 + Math.max(lh, rh);
}
max_height = Math.max(max_height, maxDepth(root.left) + maxDepth(root.right));
diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);
return max_height
}
Теперь это работает, за исключением, по-видимому, случая, когда самый длинный путь не проходит через корневой узел. Но я попытался учесть этот случай, т. е. я выполняю итерацию на каждом узле дерева:
diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);
Где я ошибаюсь? Цените любую помощь. Обратите внимание, что мне нужно оптимизировать это с O(N2) до O(N), но сейчас я просто пробую грубую силу.
Тестовый пример, для которого это не удалось, - это дерево:
Рассмотрим самый длинный путь в этом проходе от -1 до -2.
@PresidentJamesK.Polk Подумайте об этом. Я получаю результат 7, тогда как он должен быть 8 (Путь между -1 и -2): [4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2] Вот моя работа: leetcode.com/problems/diameter-of-binary-tree/submissions/…
@PresidentJamesK.Polk: Обратите внимание, что это не обязательно должно быть сбалансированное двоичное дерево. Итак, представьте себе случай, когда одно поддерево очень короткое, а другое очень высокое; вы можете получить более длинный путь, взяв две разные ветви из высокого поддерева (это означает, что вы не проходите через корень), чем если взять по одной ветви из каждого поддерева (это означает, что вы проходите).
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 2
Вам нужно начать перемещение от корня, а затем вычислить максимальное значение диаметра текущего диаметра и сложить лево + право на итерации узла, в котором вы находитесь.
function diameterOfBinaryTree(root) {
let max_height = 0;
function maxDepth(node) {
if (!node) return 0;// if our node is falsy, means no path anymore, return 0
// Assign the left of tree to leftHeight and right of tree to rightHeight
const leftHeight = maxDepth(node.left);
const rightHeight = maxDepth(node.right);
// take the max of current diameter and combination of left+right (in case path goes through root)
max_height = Math.max(diameter, leftHeight + rightHeight);
return Math.max(leftHeight, rightHeight) + 1; // add 1 to go a level above
}
maxDepth(root); // begin traversing from root
return max_height;
}
Хм, я полагаю, вы тоже хотели бы, чтобы let diameter =0 было объявлено max_height. Даже в этом случае это не работает для одного и того же тестового примера. Кроме того, мне было действительно любопытно, почему мое решение не работает.
Но я попытался учесть этот случай, т. е. я выполняю итерацию на каждом узле дерева:
diameterOfBinaryTree(root.left); diameterOfBinaryTree(root.right);Где я ошибаюсь?
Функция diameterOfBinaryTree выполняет вычисление и возвращает значение, но у нее нет никаких «побочных эффектов» — на самом деле она ничего не делает — поэтому нет причин вызывать ее и отбрасывать результат. И это хорошо! Чистые функции, подобные этой, легче рассуждать (как для людей, так и для компиляторов). Но это означает, что эти рекурсивные вызовы бессмысленны.
Вместо этого вам нужно фактически использовать результат:
return Math.max(
maxDepth(root.left) + maxDepth(root.right),
diameterOfBinaryTree(root.left),
diameterOfBinaryTree(root.right)
);
Хм, а я думал, что обновляю max_height при каждом звонке и наконец перезваниваю. Так в чем же была ошибка?
@ABGR max_height является локальным для функции; он не будет сохраняться при вызовах функций.
Ааа, теперь я немного в замешательстве :) Посмотрите это: stackoverflow.com/questions/78592674/… Была аналогичная ситуация, и я узнал, что, хотя локальный вызов каждый раз сбрасывает объявленную переменную, верхний вызывающий объект будет делать его все больше и больше по мере раскручивания рекурсии, и это имело для меня смысл. Цените свои идеи, и ваше решение будет работать идеально.
Хм, если немного подумать, все ясно. Спасибо. Вы правы, более ранние рекурсивные вызовы были фактически бессмысленными, поскольку max_height оценивался только на основе верхнего вызова. Это правильно? Так что я мог бы заставить это работать таким образом, даже если объявить max_height: max_height = Math.max(max_height, maxDepth(root.left) + maxDepth(root.right), diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right));
@ABGR: Верно — ключевое слово let означает, что для каждого вызова этой функции создается новый/отдельный max_height, и эти разные max_height не мешают друг другу. return max_height возвращает только max_height из текущего вызова. Re: «Я мог бы заставить это работать таким образом, даже с объявлением max_height»: На самом деле нет причин так делать, но да: если это важно для вас, вы можете.
Можете ли вы добавить пример двоичного дерева, для которого самый длинный путь не проходит через корень, в какой-нибудь разумной записи?