使用 C++ 删除与节点连接的边，使得三个给定节点位于不同的树中

假设我们给定一棵二叉树，以及这棵二叉树中的三个节点。我们需要将其中一个节点完全与树断开连接。断开该节点连接后，会得到三棵不同的树。这三个给定节点分别位于其中一棵树中，或者这三个给定节点都不能存在于同一棵树中。

断开节点连接意味着我们将删除该节点到所有其他节点的所有边。

示例

例如，假设我们有一棵树，其中包含三个节点 18、15 和 17，如下所示：

如果任务是删除节点 12，我们需要切断它与子树的连接，如下所示：

删除后，三棵树将为：

• T1: {14, 18, 19}

• T2: {15},

• T3: {11,12,16,17}

我们可以看到，通过断开元素 12 与树的连接，我们得到了三棵树，并且所有三个节点都位于三棵不同的树中。给定的C++ 代码显示节点 18 和 15 的最近公共祖先是 12。因此，删除 12 上方的节点将不起作用。节点 15 和 17 的 LCA 是 11，节点 18 和 17 的 LCA 是 11。

正如我们观察到的，

• LCA(18, 15) = 12

• LCA(15, 17) =11

• LCA(18, 17) = 11

我们观察到 11 出现在 (15,17) 和 (18,17) 中，删除其中一个将不起作用，因为另外两个仍然连接。12 只出现一次，断开它将断开其他两个节点的连接。断开这个节点也将断开 LCA 11 的连接。这两个节点导致了相同的 LCA，现在它们不再连接在一起。如果你在这里感到困惑，请尝试举个例子并自己解决。

所以我们只需要找到所有三个节点之间的 LCA，并选择不重复的那个。

正式地说，如果：

LCA(a, b) = l

LCA(b, c) = m

LCA(a, c) = k

那么如果 m==k，则答案为l；如果 m==k，则答案为l；如果 l==k，则答案为m。

注意：这有点难以理解，所以我建议你举一些例子并自己解决。

#include <iostream>
using namespace std;
class Node {
   public:
   int value;
   Node *left, *right;
   Node(int value) {
      this->value = value;
      left = right = NULL;
   }
};
Node* lca(Node* root, int key1, int key2) {
   if (root == NULL) {
      return NULL;
   }
   if (root->value == key1 || root->value == key2) {
      return root;
   }
   Node* llca = lca(root->left, key1, key2);
   Node* rlca = lca(root->right, key1, key2);
   if (llca && rlca) {
      return root;
   }
   return (llca != NULL) ? llca : rlca;
}
Node* solve(Node* root, int a, int b, int c) {
   Node* l = lca(root, a, b);
   Node* m = lca(root, b, c);
   Node* k = lca(root, c, a);
   if (l->value == m->value) {
      return k;
   }
   else if (l->value == k->value) {
      return m;
   }
   else {
      return l;
   }
}
int main() {
   Node* root = new Node(11);
   root->left = new Node(12);
   root->right = new Node(13);
   root->left->left = new Node(14);
   root->left->right = new Node(15);
   root->left->left->left = new Node(18);
   root->left->left->right = new Node(19);
   root->right->left = new Node(16);
   root->right->right = new Node(17);
   cout << "Disconnect node with value: " << solve(root, 18, 15, 17)->value;
   return 0;
}

输出

Disconnect node with value: 12

结论

Prateek Jangid

更新于： 2022年8月10日

149 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习