首頁 > 後端開發 > C++ > C++程式以移除不滿足路徑和大於等於k的節點

C++程式以移除不滿足路徑和大於等於k的節點

PHPz
發布: 2023-09-14 11:25:07
轉載
945 人瀏覽過

C++程式以移除不滿足路徑和大於等於k的節點

在這個問題中,我們有一個二元樹,其從根節點到葉節點的路徑是完全定義的。從根節點到葉節點的所有節點的總和必須大於或等於常數值 k。因此,我們需要刪除那些總和小於 k 的路徑中的所有節點,這樣樹中剩餘的路徑將大於 k。這裡要記住的重要一點是,一個節點可能是許多路徑的一部分,因此只有當通往該節點的所有路徑的總和

從根節點到葉子節點,我們可以計算和。當節點的遞歸呼叫完成並且控制返回時,我們可以檢查左路徑和右路徑的總和是否

假設我們有 150 K 和一棵像這樣的樹 -

                  10
                  /\
                 20 30
                /\   /\
              5  35 40 45
                 /\     /\
               50  55 60  65
                   /\  /  /
                 70 80 90 100
登入後複製

如果我們看到路徑 root->left->left 的總和為 10 20 5,即 25,小於 150,我們需要對其進行修剪並刪除 5。之後,讓我們評估 10- >30->40。它小於 150,因此刪除 40。

現在我們看到另一條路徑10->20->35->50,總和115小於150,所以我們刪除50。現在我們剩下的路徑是

10->20->35->55->70 ;
10->20->35->55->80 ;
10->30->45->60->90 ;
10->30->45->65->100 ;
登入後複製

所有路徑的總和大於150,所以我們不需要再修剪。

範例

下面是一個 C 程序,示範如何刪除不在任何路徑中且其總和大於或等於任何常數值 k 的節點 -

#include <iostream>
using namespace std;
class Node {
   public:
   int value;
   Node *left, *right;
   Node(int value) {
      this->value = value;
      left = right = NULL;
   }
};
Node* removeNodesWithPathSumLessThanK(Node* root, int k, int& sum) {
   if(root == NULL) return NULL;
   int leftSum, rightSum;
   leftSum = rightSum = sum + root->value;
   root->left = removeNodesWithPathSumLessThanK(root->left, k, leftSum);
   root->right = removeNodesWithPathSumLessThanK(root->right, k, rightSum);
   sum = max(leftSum, rightSum);
   if(sum < k) {
      free(root);
      root = NULL;
   }
   return root;
}
void printInorderTree(Node* root) {
   if(root) {
      printInorderTree(root->left);
      cout << root->value << " ";
      printInorderTree(root->right);
   }
}
int main() {
   int k = 150;
   Node* root = new Node(10);
   root->left = new Node(20);
   root->right = new Node(30);
   root->left->left = new Node(5);
   root->left->right = new Node(35);
   root->right->left = new Node(40);
   root->right->right = new Node(45);
   root->left->right->left = new Node(50);
   root->left->right->right = new Node(55);
   root->right->right->left = new Node(60);
   root->right->right->right = new Node(65);
   root->left->right->right->left = new Node(70);
   root->left->right->right->right = new Node(80);
   root->right->right->left->left = new Node(90);
   root->right->right->right->left = new Node(100);
   int sum = 0;
   cout << "Inorder tree before: ";
   printInorderTree(root);
   root = removeNodesWithPathSumLessThanK(root, k, sum);
   cout << "\nInorder tree after: ";
   printInorderTree(root);
   return 0;
}
登入後複製

輸出

Inorder tree before: 5 20 50 35 70 55 80 10 40 30 90 60 45 100 65 
Inorder tree after: 20 35 70 55 80 10 30 90 60 45 100 65 
登入後複製

我們完全修剪後的樹 -

                  10
                  / \
                 20  30
                 \     \
                 35     45
                  \     /\
                  55   60 65
                  /\    /  /
                 70 80 90 100
登入後複製

結論

正如我們所看到的,在初始觀察之後,我們可以應用 DFS 並在遞歸函數從每次呼叫返回時透過計算該節點的總和來刪除節點。總的來說,這是一個簡單的觀察和方法論問題。

以上是C++程式以移除不滿足路徑和大於等於k的節點的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:tutorialspoint.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板