вернулся только за ачивкой терминатора? 😃

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

Да в сегодняшней, но я думаю, у меня в целом с обходом беда)

Идея такая, если нет детей, то мы возвращаем значение, в если дети есть то мы идём глубже и возвращаем уже массив с средним значение. <code> var averageOfLevels = function(root, result = [root.val]) { if(root.left == null && root.right == null) { return root.val; } const left = averageOfLevels(root.left, result); const right = averageOfLevels(root.right, result); if(!Array.isArray(left) && !Array.isArray(right)) { const avg = (left + right) / 2; result.push(avg); } // если вернулся массив слева или справа, то... return result; }; </code>

Идея такая, если нет детей, то мы возвращаем значение, в если дети есть то мы идём глубже и возвращаем уже массив с средним значение. <code> var averageOfLevels = function(root, result = [root.val]) { if(root.left == null && root.right == null) { return root.val; } const left = averageOfLevels(root.left, result); const right = averageOfLevels(root.right, result); if(!Array.isArray(left) && !Array.isArray(right)) { const avg = (left + right) / 2; result.push(avg); } // если вернулся массив слева или справа, то... return result; }; </code>

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

Спасибо, буду мучать дальше

ещё может помочь такая штука, по крайней мере для меня работает: просто напиши обход как сейчас, который ничего не делает, а только печатает значение root.val и ты увидишь в каком порядке печатаются числа и намапишь на значения в дереве на картинке — сразу становится ясно в каком порядке рекурсия обходит узлы

Вот это хороший вариант для старта

вот нагляднее bfs vs dfs, мне такая иллюстрация когда-то очень помогла

вот нагляднее bfs vs dfs, мне такая иллюстрация когда-то очень помогла

Решил идти от обратного, делать не ИЗИ, а ХАРД решения для ПРО: https://leetcode.com/problems/average-of-levels-in-binary-tree/discuss/1094418/Python-short-tricky-solution-for-pros-explained

Фига выстрелило

Бабичев заапрувил. Это успех.

вот нагляднее bfs vs dfs, мне такая иллюстрация когда-то очень помогла

я сперва складывал на каждый уровень сами значения узлов, в массивы, а среднее считал в конце. но потом понял, что сами значения и не нужны, можно сразу сумму считать и количество.

Тут preorder DFS, самый популярный

var findAllConcatenatedWordsInADict = function(words) { const trie = new Trie(); function dfs(word, start, chainLen) { if (word.length == start) { // нужно убедиться, что нашли больше чем одно слово в цепочке return chainLen > 1; } let curr = trie.root; for (let i = start; i < word.length; i++) { curr = curr.get(word[i]); // если в дереве нет следующем буквы, // значит нет ни одного слова для продолжения if (!curr) { return false; } // если это лист, надо попборовать снова поискать все дерево // в поиске следующих слов, только отрезав уже найденный «префикс» if (curr.isLeaf && dfs(word, i + 1, chainLen + 1)) { return true; } } return false; } const result = []; // оптимизация, которая позволит // исключить TLE для кейса с общими префиксами: // a, aa, aaa, aaaa, aaaaa, ... // имеет смысл добавлять слова в трай постепенно, // т.к. в любом случае маленькие слова нельзя побить большими, // соответственно и в дереве они раньше времени не нужны words.sort((a, b) => a.length - b.length); words.forEach((word) => { if (dfs(word, 0, 0)) { result.push(word); } else { trie.add(word); } }); return result; }; class Trie { root = new Node("") add(word) { let curr = this.root; for (let i = 0; i < word.length; i++) { curr = curr.add(word[i]); } curr.isLeaf = true; } } class Node { isLeaf = false; children = new Array(26); constructor(val) { this.val = val; } add(val) { const idx = this.idx(val); if (!this.children[idx]) { this.children[idx] = new Node(val); } return this.children[idx]; } get(val) { return this.children[this.idx(val)]; } idx(val) { return val.charCodeAt(0) - 'a'.charCodeAt(0); } }

Подскажи, пожалуйста, зачем разные типы обходов? In, pre, post, от задач зависит?

Подскажи, пожалуйста, зачем разные типы обходов? In, pre, post, от задач зависит?

Или например BST + inorder, чтобы вывести значения в отсортированном порядке, полезно знать :)

Спасибо, порешаю)

а давно в литкоде появились визуалайзеры?

А у меня ноут отобрали, а на новую работу ещё не анборднулся, решаю с телефона литкод чтобы страйк не пропал

неплохо. я выкупил свой когда увольнялся.

хорошо, когда такая возможность есть

ага, вроде в Яндексе это стандартная практика.

Хз, мне не дали выкупить, как я понял можно выкупать только старые модели

именно. в 2018 году купил, по-моему, за 34 тысячи рублей, MacBook Pro (Retina, 13-inch, Mid 2014)

неплохо. я выкупил свой когда увольнялся.

Хз, мне не дали выкупить, как я понял можно выкупать только старые модели

Так вроде именно свой нельзя. Выкупаешь со скидкой?

ну, свой — который был у меня тогда на руках. рабочий.

со скидкой, да.

Ладно, завтра пойду работать, почитаю на вики

Даже в выходной работать?

Даже в выходной работать?

человеку 20 лет, как же иначе!

Мне не понять. В 20 лет вокруг много интересного помимо работы. Ну, во всяком случае у меня так было

Мне не понять. В 20 лет вокруг много интересного помимо работы. Ну, во всяком случае у меня так было

А потом академ возьму, чтобы еще по карьериться годик, только уже в Гугле

Какие-то страшные вещи говоришь, что может быть интереснее литкода 😂

может закончить лучше сперва? 😄