Максимальная абсолютная разница между родственными узлами данного BST
Учитывая BST (бинарное дерево поиска) с N узлами, задача состоит в том, чтобы найти максимальную абсолютную разницу между одноуровневыми узлами.
Two nodes are said to be siblings if they are present at the same level, and their parents are the same.]
Примеры :
Input:
Diagram 1 for Ex-1
Output: 70
Explanation:
105 – 50 = 55 (As 105 and 50 nodes are siblings)
75 – 5 = 70 (As 75 and 5 nodes are siblings)
106 – 101 = 5 (As 106 and 5 nodes are siblings)
Other than these, there is no other pair of nodes that are siblings.
So among them the max difference is 70. (75 – 5 = 70)Input:
Diagram 2 for Ex-2
Output: 60
Explanation:
120 – 60 = 60
90 – 45 = 45
160 – 110 = 50
Other than these, there is no other pair of nodes that are siblings.
So among them the max difference is 60. (120 – 60 = 60)
Подход:
The basic Idea is to check whether the nodes are siblings or not if sibling then find out the maximum difference.
Следуйте шагам, указанным ниже, чтобы реализовать идею:
- Повторите BST в режиме предварительного заказа. Корень слева направо.
- В каждой точке,
- Проверьте, доступны ли левый и правый потомки.
- Если доступны оба, вычислите разницу между правым и левым значениями. (По умолчанию BST правое значение > левое значение)
- Максимизируйте абсолютную максимальную разницу.
- В противном случае просто продолжайте обход.
- После завершения обхода верните максимальную разницу между одноуровневыми узлами.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(h)
Статьи по Теме:
- Введение в двоичное дерево поиска — учебные пособия по структуре данных и алгоритмам
- Вставка в двоичное дерево поиска