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

Question

设 T 为树

对于节点 (1)，最小祖先为 6。对于节点 (3)，最小祖先为 12。我正在尝试编写一个递归解决方案，returns 的最小祖先一个节点。

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

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

如果找到目标，return最小值。

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

Answer 2

你可以通过执行BFSs（或DFSs，并不重要）来解决它，并且每个节点都应该携带所有祖先的最小值。例如：

               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] 应该 return 到 DFS 末尾的任何节点 u 的右最小祖先（根除外，其最小祖先本身就是）。

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

How to get the minimum ancestor of a node in a binary tree

c

algorithm

binary-tree