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

Answer 2

你可以通过执行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]应返回在 DFS 末尾u的任何节点的正确最小祖先(根除外，其最小祖先是其自身(。