Я справился с недавней проблемой кода и хотел написать об этом. Задача заключалась в том, чтобы оценить дерево и определить узлы, у которых нет родителей или есть только один родитель. Данные будут представлены вам в виде 2D-массива и будут выглядеть примерно так:

1   4   8   10
 \ / \ / \ /
  3   5   2
 /     \
7       9

В этом примере узлы 1, 4, 8 и 10 не имеют родителей. Узлы 7 и 9 имеют только одного родителя.

Так как бы нам это сделать?

Есть много подходов, но простой подход - просто использовать HashMap для сопоставления дерева и количества родителей. Затем используйте этот HashMap, чтобы понять ситуации, когда у вас есть один родитель и нет родителей.

Вот полный код (включая основной метод):

Если вы заметили, данные передаются в виде 2D-массива. Двумерный массив всегда будет только глубины 2, поэтому этот код использует это преимущество в начальном цикле for, где он добавляет значение в HashMap с родительской суммой 1 при первом его обнаружении, а затем делает его общим из 2, если он найден снова:

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

В этом коде показан один из методов использования HashMap, но во многих случаях конкретные языки предлагают настраиваемые классы, которые принудительно устанавливают порядок или другие полезные механизмы. Ознакомьтесь с этим кодом самостоятельно и зайдите в Google Java HashMaps, чтобы найти другие интересные статьи по этой теме.

Первоначально опубликовано на https://rhythmandbinary.com 1 мая 2019 г.