вроде не

Речь не о корректности результата, а о том что нода попадает в очередь тем больше раз чем она дальше от листа

аааа,я понял

типа root.left.left.left ?

Тип нода слева от рута попадет в очередь на каждом следующем цикле

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

а по другому вроде как и нельзя написать

?

Нет, ты должен перебирать только текущий уровень потом создавать новую очередь и тд

Ну либо написать рекурсию и не парить себе мозг

Те не писать бфс, а перейти к дфс и не париться

Вообще полезно находить худший случай для своего алгоритма, отмазки в стиле проходит все тесты, это как у меня на машине работало, некст левел. Уже чуть лучше, но все еще плохой подход)

мне теории не хватает, я не знал что такое бфс и дфс до того как только что погуглил

ща напишу рекурсию

Добрался до компа ;)

добрался до компа ... чет я вообще не пойму как у тебя работает ;) ты попаешь ноду а после этого аппендишь в конец. когда ты будешь следующий раз попать .. ты же попнешь уже добавленную ноду ... чет я "поплыл"

добрался до компа ... чет я вообще не пойму как у тебя работает ;) ты попаешь ноду а после этого аппендишь в конец. когда ты будешь следующий раз попать .. ты же попнешь уже добавленную ноду ... чет я "поплыл"

в процессе фор происходит замена предыдущего уровня дерева следующим

а поп(0) каждый раз перестраивает массив

что опять же ведет к квадрату ...

когда у тебя в массиве n элементов ... то чтобы сделать pop(0) нужно сделать n-1 присваивание

когда у тебя в массиве n элементов ... то чтобы сделать pop(0) нужно сделать n-1 присваивание

я не знал :)

ну тут легко пофиксить возьми деку

сука ... deque гугли в коллекшнах

импортировать - это читерство

и вместо pop(0) делаешь popleft

это стандартная библиотека

ну или не попай итерируй старый массив и создавай новый ... потом меняй их местами

т.е аппенщишь в nextnodes а в конце делаешь nodes = nextnodes

В принципе решение норм. Есть нюансы но они фиксятся легко и на не больших объемах не критично, когда глянул в дороге показалось вообще бред. "извините был напуган" ;)

в общем, сам рекурсию я не потянул, подсмотрел в дискашенс https://dpaste.org/fedbD

ой, каунтер забыл убрать

спасибо

т.е аппенщишь в nextnodes а в конце делаешь nodes = nextnodes

https://dpaste.org/ogTCx

https://dpaste.org/ogTCx

я кстати изначально так хотел, но думал с поп красивее получится

не знал что поп за линейное время работает, если убирать не последний элемент

@ikovrigin https://leetcode.com/problems/average-of-levels-in-binary-tree/ https://dpaste.org/azag6 вот такая еще есть, тут не понятно как рекурсию использовать

не знал что поп за линейное время работает, если убирать не последний элемент

Смотря где, вроде в list() так и работает, линия

Смотря где, вроде в list() так и работает, линия

если последний элемент убирать - О(1)

@ikovrigin https://leetcode.com/problems/average-of-levels-in-binary-tree/ https://dpaste.org/azag6 вот такая еще есть, тут не понятно как рекурсию использовать

ой, тут поп забыл переделать

ща

@ikovrigin https://leetcode.com/problems/average-of-levels-in-binary-tree/ https://dpaste.org/azag6 вот такая еще есть, тут не понятно как рекурсию использовать

В рекурсии отслеживаешь текущий уровень накапливаеш по уровню сумму и количество в конце делишь

если последний элемент убирать - О(1)

Не добавил контекст, я про случай, когда указываешь элемент не последний Но в той же deque pop() крайних элементов это O(1)

Как вариант, ты можешь свою deque написать, если у тебя будет фикс.размер, то тоже получишь pop за линию, даже лучше понять, как это работает

ой, тут поп забыл переделать

https://dpaste.org/EuEk3

Угу. Ну какие то простые обходы дерева аж скучно ;)

Угу. Ну какие то простые обходы дерева аж скучно ;)

а последнее решение, которое я скинул, тоже квадрат же?

я запутался

нет че квадрат только если не правильно обрабатывать список ... в остальных случаях у тебя линия ... все обходы это линия при нормальном написании.

Ты в каждую ноду приходишь один раз. Делаешь фиксированное кол-во действий . Соответсвенно это линия.

типа root.left.left.left ?

меня вот эта тема запутала

Та я ж говорю я тупанул ... я в дороге не понял что ты попаешь

меня вот эта тема запутала

Смотри когда ты обходишь DFS то худший случай это большая глубина ... а когда bfs то большая ширина. Худший в плане памяти . По времени что в том что в том случае будет N

Поэтому просто в каждом конкретном случае берешь какой обход удобнее тот и используешь.

Но для большинства задач вообще пофиг бфс или дфс

def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]: levels = [] def rec(node, lvl): if len(levels) <= lvl: levels.append([0,0]) levels[lvl][0] += 1 levels[lvl][1] += node.val if node.left: rec(node.left, lvl + 1) if node.right: rec(node.right, lvl + 1) rec(root, 0) return [s/cnt for cnt, s in levels]

с dfs та же задача

Мне вообще кажется что у этих задач медиум сложность только потому что люди боятся деревьев ;)

107 задача то же самое ... даже среднее считаь не нужно просто числа пихануть в массив вот с какого перепуга она медиум

блять почему нельзя нормально называть переменные, в дискашенс постоянно что-то вырвиглазное творится

Всем здаров, давно не виделись. Че, как?

блять почему нельзя нормально называть переменные, в дискашенс постоянно что-то вырвиглазное творится

Дискашенс?

Дискашенс?

литкод

литкод

Пон

ребят, привет, поделитесь, пожалуйста книжкой тони гэддис - начинаем программировать на питон, 5 издание?

ребят, привет, поделитесь, пожалуйста книжкой тони гэддис - начинаем программировать на питон, 5 издание?

я бы на твоем месте не парился и скачал укус питона, он в открытом доступе лежит

если хочешь именно тонни гэддиса, скачай 4 издание, вряд ли есть большая разница. 5 ты вряд ли найдешь слитым, он только в этом году вышел

ребят, привет, поделитесь, пожалуйста книжкой тони гэддис - начинаем программировать на питон, 5 издание?

https://vk.com/wall-203365865_814

если хочешь именно тонни гэддиса, скачай 4 издание, вряд ли есть большая разница. 5 ты вряд ли найдешь слитым, он только в этом году вышел

укус был, но посоветовал не один человек гэддиса начать)

https://vk.com/wall-203365865_814

спасибо мил человек😎

С чем связаны непонятные картинки на обложках книг по программированию ?

С чем связаны непонятные картинки на обложках книг по программированию ?

чем тебе не понятен гранат?

чем тебе не понятен гранат?

А причём здесь гранат ?

Либо слон, вот причём слон и программирование по С++ ?

А причём здесь гранат ?

да просто чтоб было проще идентифицировать наверное. "скачай книжку с гранатом на обложке"

маркетинг все дела

С чем связаны непонятные картинки на обложках книг по программированию ?

если умеешь распознавать картинки на обложке, значит настало время учиться програмировать

С чего начать обучаться программированию на андроид?

С чем связаны непонятные картинки на обложках книг по программированию ?

Гранат == ООП

Обьект класса зерно наследует обьект класса гранат