«Сделай сам: расстояние K для всех узлов в двоичном дереве» — это формулировка задачи кода в Scala. Задача состоит в том, чтобы найти все узлы бинарного дерева, находящиеся на расстоянии K от заданного целевого узла. Вот несколько способов решения этой проблемы:

Метод 1: поиск в глубину (DFS) с родительскими указателями

1. Перейти по двоичному дереву и назначить родительские указатели каждому узлу.
2. Выполните поиск в глубину от целевого узла, чтобы найти все узлы на расстоянии K.
3. Во время DFS сохраняйте посещенный набор, чтобы избежать повторного посещения узлов.
4. Когда расстояние K будет достигнуто, добавьте текущий узел в набор результатов.
5. Рекурсивно обойти левое и правое поддеревья текущего узла, исключая родительский узел, с уменьшенным расстоянием K – 1.

Метод 2: поиск в ширину (BFS) с отслеживанием уровней

1. Выполнить поиск в ширину, начиная с целевого узла.
2. Поддерживайте очередь для хранения узлов и трекер уровня для отслеживания расстояния от целевого узла.
3. Извлеките узел из очереди, проверьте, соответствует ли его уровень K, и добавьте его в набор результатов, если это правда.
4. Поставьте в очередь левый и правый дочерние узлы выведенного из очереди узла с увеличенным уровнем.
5. Повторяйте шаги 3–4, пока очередь не станет пустой.

Метод 3: рекурсивный подход

1. Начните со вспомогательной функции, которая находит все узлы на расстоянии K в левом и правом поддеревьях данного узла.
2. Рекурсия по левому и правому дочерним узлам, каждый раз уменьшая расстояние на 1.
3. Когда расстояние достигнет 0, добавьте текущий узел в набор результатов.
4. Кроме того, проверьте, присутствует ли целевой узел в левом или правом поддереве. Если да, рекурсивно найти узлы на расстоянии K от целевого узла в противоположном поддереве.