c - 如何获取二叉树中节点的最小祖先

Question

让 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;
}

我能够到达给定目标节点的每个祖先节点，但我不知道如何获得这些节点的最小值。

Answer 1

当您遍历树时，请跟踪您在该路径上找到的最小值。这可以通过添加第三个参数轻松完成，这是目前发现的最小值。

如果找到目标，返回最小值。

如果到达一片叶子，返回 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);
}