Любые задачи на дерево решаются через BFS или DFS. Или обход в ширину, или в глубину. Тут, очевидно, в глубину. Такую задачу дают на собесах в Гугл и Амазон. Не знаю, кто начал раньше. Решение - отличное! Интересно было посмотреть, как оно на Scala реализуется. Спасибо за контент!
Лет пять назад собеседовался в яндекс, после созвона с HR было онлайн-интервью с разрабом и одной из задач он меня как раз просил посчитать максимальную сумму ветки) Ничего не меняется) забавно, но помню, как будто бы вчера было)
дак если дерево - это рекурсивная структура, то как тогда мы можем идти снизу вверх, если число конечных узлов не известно? почему нельзя идти сверху вниз, и если мы к примеру знаем максимальное число, которое способно содержать узел (видимо 9 в этой задаче), понимать, идти ли нам дальше вглубь, или нет
А кстати, это решение подразумевает упрощенное понимание - найти ветку с наибольшей суммой узлов. Ведь так сами узлы остаются не найдеными, а найдена только сумма. Просто пытаюсь модифицировать этот алгоритм на поиск самих значений узлов и пока не получается придумать как это сделать, хотя должно быть не сложно.. но из-за его рекурсивности, видимо, не получается
есть второе видео, где мы ломаем данное решение, там будет проще сделать то что Вы хотите ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-0_4cgLGSmKA.html
Вот смотрю я на этот Scala, рассказываете про его фишечки типа параметры по умолчанию, sealed, object и понимаю, что эти штуки есть в Kotlin. Scala появился в 2003г., Kotlin - в 2011г. Похоже, что Kotlin у них позаимствовал некоторые вещи.
Проходил собеседование в Microsoft. Спрашивали больше об абстрактном понимании рекурсии и многопоточности. Когда yandex в последний раз видел деревья на интерпрайзе?
Не совсем понятно: в начале вы сказали что нужно найти ветку с максимальной суммой, а нашли сумму чисел в ветке с максимальной суммой. Если гооврить строго то ответ должен представлять собой перечисление идентификаторов узлов дерева по которым нашлась максимальная сумма, это потребует модификации метода MAX - но алгоритм по сути будет то же.
Очень точно подмечено)) Я и сам в начале хотел найти саму ветку, вернуть список узлов на ней. Но решил не переусложнять алгоритм, и уже на этапе монтажа понял что чутка по другому решил задачу Но думаю это не прям серьезно - как Вы правильно заметили, алгоритм довольно легко доработать чтобы он возвращал и саму ветку тоже
@@igorromanenko336 вообще, я бы перед решением уточнил, что в ответе нужно вернуть: просто сумму или прям саму ветку? Но поскольку мне не у кого спросить, я подумал, что наверное это усложнённая задача и имелась в виду сумма. Так что не душнила. Нормально подмечено.
Решение будет некорректным в случае наличия отрицательных ключей в дереве. Тогда максимальное поддерево не обязано начинаться корнем. В случае неотрицательных ключей такая ветка всегда будет начинаться от корня
А вот мое решение на VBA, тоже рекурсивное. Оно учитывает варианты когда веса заданы отрицательные. И собирает в один лист (коллекцию) все узлы максимальной ветки: Public Function FindMaxBranch(BinTree As BinTreeNode, _ Optional ByRef total As Long) As Collection Dim ListL As Collection, ListR As Collection Dim totalL As Long, totalR As Long If BinTree Is Nothing Then Exit Function Set ListL = FindMaxBranch(BinTree.Left, totalL) Set ListR = FindMaxBranch(BinTree.Right, totalR) total = totalL Select Case True Case ListL Is Nothing And ListR Is Nothing: Set FindMaxBranch = New Collection Case ListR Is Nothing: Set FindMaxBranch = ListL Case ListL Is Nothing Or totalR > totalL: Set FindMaxBranch = ListR: total = totalR Case Else: Set FindMaxBranch = ListL End Select FindMaxBranch.Add BinTree total = total + BinTree.Weight End Function
А разве бинарное дерево со взвешенными узлами не означает, что есть узлы, и каждый узел нужно взвесить определённым числом. и получается суммировать не сами числа в узлах, а число, умноженное на его вес?
@@wolf_code Извиняюсь.. Это я ошибся.. Я думал, что есть просто дерево, и на каждом узле свой вес, отличный от значения этого узла должен быть.. а на самом деле значение узла и есть вес этого узла. А не взвешенное бинарное дерево, это когда веса каждого узла равны, и тогда поиск наибольшей суммы по ветке равен ветке с наибольшим количеством узлов.
А нельзя было просто пройтись поиском в ширину, добавляя значения из родительских узлов в дочерние? Плюс две переменные, хранящие максимальную известную на данный момент сумму и индекс соответствующего узла.
я бы решал от корня к листьям и потом взял бы максимум от всех листьев. Но так даже красивее) Хотел сказать я, но вспомнил про рекурсию. Я предпочитаю деревья упаковывать в массив, так можно обойтись без рекурсии. Достаточно понимать, что индекс корня = 1, а индекс потомков любой ноды = 2i и 2i+1.
Вы наверное имели ввиду что значения узлов в левом поддереве должно быть меньше чем в правом? Не совсем, то о чем вы говорите это бинарное дерево поиска, а на видео просто бинарное дерево
