Проверить, являются ли два бинарных дерева зеркальными | Набор 3

Опубликовано: 22 Сентября, 2022

Имея два массива, A[] и B[] , состоящие из M пар, представляющих ребра двух бинарных деревьев из N различных узлов в соответствии с обходом в порядке уровней, задача состоит в том, чтобы проверить, являются ли деревья зеркальными отображениями друг друга.

Примеры:

Input: N = 6, M = 5, A[][2] = {{1, 5}, {1, 4}, {5, 7}, {5, 8}, {4, 9}}, B[][2] = {{1, 4}, {1, 5}, {4, 9}, {5, 8}, {5, 7}}
Output: Yes
Explanation:

Example 1

Input: N = 5, M = 4, A[][2] = {{10, 20}, {10, 30}, {20, 40}, {20, 50}}, B[][2] = {{10, 30}, {10, 20}, {20, 40}, {20, 50}}
Output: No
Explanation:

Example 2

Набор 1 и набор 2 этой статьи обсуждались в предыдущих статьях.

Подход: Данная проблема может быть решена с использованием структур данных Map и Set. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте два, карты векторов говорят T1 и T2 для хранения списка смежности деревьев A и B соответственно.
  • Инициализируйте набор, скажем, St , чтобы хранить все уникальные значения узлов.
  • Пройдите массив A[] , используя переменную i и выполнив следующие шаги:
    • Поместите значение A[i][1] в вектор T1[A[i][0]] , а затем добавьте A[i][0] и A[i][1] к набору St .
  • Поскольку ребра задаются в соответствии с обходом порядка уровней, поэтому в дереве A для всех узлов сначала был вставлен левый дочерний элемент, а затем правый дочерний элемент.
  • Пройдите массив B[] в обратном порядке, используя переменную i и выполнив следующие шаги:
    • Поместите значение B[i][1] в вектор T2[B[i][0]] и затем добавьте B[i][0] и B[i][1] к набору St .
  • Поскольку массив B[] просматривается в обратном порядке, поэтому в дереве B для всех узлов сначала был вставлен правый дочерний элемент, а затем левый дочерний элемент.
  • Теперь выполните итерацию по набору St и проверьте, не равны ли векторы дочерних элементов текущего узла в дереве A векторам дочерних элементов текущего узла в дереве B , затем выведите « Нет » в качестве ответа и затем вернитесь.
  • Наконец, если ни один из вышеперечисленных случаев не удовлетворяет, то в качестве ответа выведите « Да ».

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O((N+M)*log(N))
Вспомогательное пространство: O(N+M)

РЕКОМЕНДУЕМЫЕ СТАТЬИ