Поиск точки седла в двоичном дереве с использованием рекурсии

Question

Я хочу найти седловую точку T, двоичного дерева, если таковой имеется. Седло-точка имеет минимальное значение среди всех своих предков, но она имеет максимальную ценность среди всех ее потомков. Лист может быть такой седловой точкой, если он имеет меньшее значение, чем все его предки.

Примера дерево:

   F:15 
     E:16  H:17 
    B:14   G:16 I:8 
A:8 C:7 
      D:5 

В является одним из такой седловой точки, потому что 14 меньше, чем 16 и 15, но также больше, чем 8, 7 и 5. А, С, D, и я являюсь другие точки седла.

Я попытался придумать способ рекурсивно проверить каждый из под деревьев и доказать, что родительский узел является максимальным среди всех его потомков. Но поскольку C (16) является максимальным среди всех его потомков, но больше F (15), он не является седловой точкой, поэтому этот метод неверен.

Какой был бы лучший способ решить эту проблему?

Answer 1

Запишите функцию find_saddle, которая берет узел и минимальное значение родителей (по умолчанию для корневого узла - INT_MAX). Он вернет значение самого большого ребенка. Когда функция вызывается, она вычисляет наибольшее значение, которое может иметь ребенок, и потенциально может быть седлом, минимальным значением самого себя и минимальным родителем. Затем он повторяется с этим минимумом слева и справа и получает максимальные значения в каждом поддереве. Если собственное значение узла больше, чем max max подстроки болтов, но меньше минимальных значений родителя, то это седло и делает ... все, что вы хотите. Наконец, он возвращает максимум своего значения и оба максимума поддерева.

int find_saddle(node* n, int parent_min=INT_MAX) { 
    int child_min = min(n->value, parent_min); 

    int left_max = INT_MIN; 
    if (n->left) 
     left_max = find_saddle(n->left, child_min); 

    int right_max= INT_MIN; 
    if (n->right) 
     right_max = find_saddle(n->right, child_min); 

    int child_max = max(left_max, right_max); 

    if (n->value > child_max && n->value < parent_min) 
     do_thing(n); 

    return max(child_max, n->value); 
} 

Этот код предполагает, что листья могут быть седлами, но это не очень трудно настроить его, чтобы исключить те узлы.