C++-Programm zum Entfernen von Knoten, die den Pfad nicht erfüllen und größer oder gleich k sind

In diesem Problem haben wir einen Binärbaum, dessen Pfad vom Wurzelknoten zum Blattknoten vollständig definiert ist. Die Summe aller Knoten vom Wurzelknoten bis zu den Blattknoten muss größer oder gleich dem konstanten Wert k sein. Daher müssen wir alle Knoten in den Pfaden entfernen, deren Summe kleiner als k ist, damit die verbleibenden Pfade im Baum größer als k sind. Hierbei ist zu beachten, dass ein Knoten Teil vieler Pfade sein kann. Daher werden solche Knoten nur entfernt, wenn die Summe aller zu diesem Knoten führenden Pfade

Vom Wurzelknoten bis zu den Blattknoten können wir die Summe berechnen. Wenn der rekursive Aufruf des Knotens abgeschlossen ist und die Kontrolle zurückkehrt, können wir prüfen, ob die Summe der linken und rechten Pfade

Angenommen, wir haben 150.000 und einen Baum wie diesen –

                  10
                  /\
                 20 30
                /\   /\
              5  35 40 45
                 /\     /\
               50  55 60  65
                   /\  /  /
                 70 80 90 100

Wenn wir sehen, dass die Summe des Pfades root->left->left 10 + 20 + 5 ist, also 25, also weniger als 150, müssen wir sie beschneiden und 5 entfernen. Danach werten wir 10->30->40 aus. Der Wert liegt unter 150, daher wird 40 gelöscht.

Jetzt sehen wir einen anderen Pfad 10->20->35->50, die Summe von 115 ist kleiner als 150, also löschen wir 50. Nun ist unser verbleibender Weg

10->20->35->55->70 ;
10->20->35->55->80 ;
10->30->45->60->90 ;
10->30->45->65->100 ;

Die Summe aller Pfade ist größer als 150, daher müssen wir nicht mehr beschneiden.

Beispiel

Hier ist ein C++-Programm, das zeigt, wie Knoten entfernt werden, die sich in keinem Pfad befinden und deren Summe größer oder gleich einem konstanten Wert k ist -

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

Ausgabe

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 

Unser vollständig beschnittener Baum -

                  10
                  / \
                 20  30
                 \     \
                 35     45
                  \     /\
                  55   60 65
                  /\    /  /
                 70 80 90 100

Fazit

Wie wir nach der ersten Beobachtung sehen können, können wir DFS anwenden und Knoten entfernen, indem wir die Summe dieses Knotens berechnen, wenn die rekursive Funktion bei jedem Aufruf zurückkehrt. Im Großen und Ganzen ist dies eine einfache Frage der Beobachtung und Methodik.

Das obige ist der detaillierte Inhalt vonC++-Programm zum Entfernen von Knoten, die den Pfad nicht erfüllen und größer oder gleich k sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!