Задача: 779. K-th Symbol in Grammar Сложность: medium Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10. Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110. Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк. Пример: Input: n = 1, k = 1 Output: 0 Explanation: row 1: 0 👨‍💻 Алгоритм: 1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal. 2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal). 3⃣В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal). 😎 Решение: class Solution { depthFirstSearch(n, k, rootVal) { if (n === 1) return rootVal; const totalNodes = 1 << (n - 1); if (k > totalNodes / 2) { const nextRootVal = rootVal === 0 ? 1 : 0; return this.depthFirstSearch(n - 1, k - totalNodes / 2, nextRootVal); } else { const nextRootVal = rootVal === 0 ? 0 : 1; return this.depthFirstSearch(n - 1, k, nextRootVal); } } kthGrammar(n, k) { return this.depthFirstSearch(n, k, 0); } } Ставь 👍 и забирай 📚 Базу знаний