使用 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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習