Как получить минимального предка узла в двоичном дереве - PullRequest
Новая
       12

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

0 голосов
/ 09 октября 2019

Пусть T будет деревом 

           12
       6        3
   13
1     14

Для узла (1) минимальный предок будет 6. Для узла (3) минимальный предок будет 12. Я пытаюсь написатьрекурсивное решение, которое возвращает минимального предка узла. 

int MinParent(struct Node *root, struct Node *target) {
    if (root == NULL) {
        return INT_MAX;
    }

    if (root->data == target->data) {
        return INT_MAX;
    }

    int res = root->data;

    if ((MinParent(root->left, target) == INT_MAX) || (MinParent(root->right, target) == INT_MAX)) {
        int res = min(??);

        return ??;
    }

    return res;
}

Я могу добраться до каждого узла-предка для данного целевого узла, но не могу понять, как получить минимум для этих узлов.

Ответы [ 2 ]

1 голос
/ 09 октября 2019

Вы можете решить это, выполнив BFS (или DFS, на самом деле не имеет значения), и каждый узел должен нести минимальное значение всех предков. Например: 

               3(3)
           5(3)    6(3)
        2(3)
     1(2)  4(2)

Чтобы сохранить ответы для всех узлов, давайте создадим карту minimumAncestor.

Для данного узла u алгоритм оценки всех минимальныхПредки всех узлов в поддеревьях с корнем в u это: 

DFS(u, minimumInAncestors){
    minimumAncestor[u] = minimumInAncestors;
    foreach child v of u:
        DFS(v, min(u, minimumInAncestors));
}

Чтобы заполнить карту, вы вызываете DFS(root, root).

. Делая это, карта minimumAncestor[u]должен возвращать правильного минимального предка любого узла u к концу DFS (за исключением корня, минимальным предком которого является сам).

1 голос
/ 09 октября 2019

При прохождении дерева следите за минимумом, который вы нашли на этом пути. Это можно легко сделать, добавив третий аргумент, минимальный найденный до сих пор.

Если вы найдете цель, верните минимум.

Если вы достигнете листа, верните INTMAX. 

int MinParent_(struct Node *node, int target, int min) {
   if (node == NULL)
      return INTMAX;

   if (node->data == target)
      return min;

   if (node->data < min)
      min = node->data;

   int rv = MinParent_(node->left, target, min);
   if (rv != INTMAX)
      return rv;

   return MinParent_(node->right, target, min);
}

int MinParent(struct Node *root, int target) {
   return MinParent_(root, target, INTMAX);
}

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

struct Node *MinParent_(struct Node *node, int target, struct Node *min_node) {
   if (node == NULL)
      return NULL;

   if (node->data == target)
      return min_node;

   if (!min_node || node->data < min_node->data)
      min_node = node;

   struct Node *rv = MinParent_(node->left, target, min_node);
   if (rv)
      return rv;

   return MinParent_(node->right, target, min_node);
}

struct Node *MinParent(struct Node *root, int target) {
   return MinParent_(root, target, NULL);
}
...