Verwenden Sie C++, um alle Knoten zu löschen, die sich auf keinem Pfad befinden und deren Pfadsumme kleiner als k ist

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 k sein. Wir müssen also alle Knoten im Pfad löschen, deren Summe kleiner als k ist. Hierbei ist zu beachten, dass ein Knoten Teil vieler Pfade sein kann. Daher werden solche Knoten nur entfernt, wenn die Summe aller 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 K 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 Pfads root->left->left 10 + 20 + 5 ist, also 25, was weniger als 150 ist, brauchen wir um es zu beschneiden und zu löschen 5. Danach werten wir 10->30->40 aus. Es ist weniger als 150, also streichen Sie 40. Jetzt sehen wir einen anderen Pfad 10->20->35->50, die Summe von 115 ist kleiner als 150, also löschen wir 50. Jetzt sind unsere verbleibenden Pfade

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, sodass wir nicht mehr beschneiden müssen.

Beispiel

#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

Schlussfolgerung

Wie wir sehen können, können wir nach der ersten Beobachtung DFS anwenden und die rekursive Funktion übergeben, wenn sie von jedem Aufruf zurückkommt. Berechnen Sie die Summe von diesen Knoten, um den Knoten zu entfernen. Im Großen und Ganzen ist dies eine einfache Frage der Beobachtung und Methodik.

Das obige ist der detaillierte Inhalt vonVerwenden Sie C++, um alle Knoten zu löschen, die sich auf keinem Pfad befinden und deren Pfadsumme kleiner als k ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!